冶炼金属

发表于 更新于 分类于 阅读次数： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

题目描述

1
2
3
4
5
6
7
8
9
10
11

小蓝有一个神奇的炉子用于将普通金属 O冶炼成为一种特殊金属 X。

这个炉子有一个称作转换率的属性 V，V是一个正整数，这意味着消耗 V  个普通金属 O  恰好可以冶炼出一个特殊金属 X ，当普通金属 O  的数目不足 V  时，无法继续冶炼。

现在给出了 N  条冶炼记录，每条记录中包含两个整数 A  和 B ，这表示本次投入了 A  个普通金属 O ，最终冶炼出了 B  个特殊金属 X 。

每条记录都是独立的，这意味着上一次没消耗完的普通金属 O  不会累加到下一次的冶炼当中。

根据这 N  条冶炼记录，请你推测出转换率 V  的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

输入格式

1
输出两个整数，分别表示 V  可能的最小值和最大值，中间用空格分开。

数据范围

1
2
3
对于 30% 的评测用例，1≤N≤10^2。
对于 60% 的评测用例，1≤N ≤10^3。
对于 100% 的评测用例，1≤N ≤10^4，1≤B≤A ≤10^9。

输入样例

1
2
3
4
3
75 3
53 2
59 2

输出样例

1
20 25

样例解释

1
2
3
4
5
6
 当 V =20 时，有：⌊75/20⌋=3，⌊53/20⌋=2，⌊59/20⌋=2，可以看到符合所有冶炼记录。

当 V=25 时，有：⌊75/25⌋=3，⌊53/25⌋=2，⌊59/25⌋=2，可以看到符合所有冶炼记录。

且再也找不到比 20 更小或者比 25 更大的符合条件的 V 值了。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
int main()
{
     int n;
     cin>>n;
     int r=2e9,l=0;
    for (int i = 0; i < n; i ++ )
    {
        int a,b;
        cin>>a>>b;
        r=min(r,a/b),l=max(l,a/(b+1)+1);
    }
    cout<<l<<' '<<r<<endl;
    
    return 0;
}

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
解题思路：

我们已知转化率为V，则a个金属O可以冶炼成为b个金属X(这时候多余的废料肯定在0~V之间)。换句话来说，炼制b个金属X最少需要消耗b*v，那么就有b*V≤a

由于a个金属O只能冶炼成为b个金属X，冶炼不出来b+1个金属X，则a<(b+1)*V

那么我们整理一下就得到一个不等式，也就是

b*V≤a<(b+1)*V

整理一下我们最后得到的不等式为

a/(b+1) <V ≤a/b

这里我们需要知道V的最小应该为(a/(b+1))+1,因为a/(b+1)<V,而不是a/(b+1)≤V。
那么接下来该写代码，我们需要定义左右边界，也就是l，r。我们需要初始化l和r，为了保证我们的初始化有效，我们需要将l初始化成为无穷大，r初始化成为无穷小。然后我们需要将左边的边界不断向符合条件的左边界的最右边逼近，意思就是所有的左边界里面最大的，而右边界和左边界完全相反，是所有的右边界里面最小的。
这一步骤也就是代码段里面的
 r=min(r,a/b),l=max(l,a/(b+1)+1);
等所有的循环完了之后再把l和r输出就行了

解题思路(二分)

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
 
int get(int a,int b)
{
    int l=1,r=1e9+10;
    while(l<r)
    {
        int mid=l+r>>1;
        if(a/mid>b) l=mid+1;
        else r=mid;
    }
    return r;
}
int main()
{
     int n;
     cin>>n;
     int r=2e9,l=0;
    for (int i = 0; i < n; i ++ )
    {
        int a,b;
        cin>>a>>b;
        r=min(r,get(a,b-1)-1);
        l=max(l,get(a,b));
    }
    cout<<l<<' '<<r<<endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
本题和上面的数学的解法唯一的区别就是
数学解法这里是
  r=min(r,a/b),l=max(l,a/(b+1)+1);
而二分的是
r=min(r,get(a,b-1)-1);
l=max(l,get(a,b));

对于get(int a,int b)函数的整体的思路是先抄一下二分的模板，再分析一下当mid满足的时候，是l=mid+1还是r=mid。
我们这里进行分析
当a/mid>b时，说明当前的转化率mid符合条件，我们需要将左边界移动到mid+1(因为mid符合条件，所以我们需要将左边界移动到mid+1)，最后我们返回的r就是需要答案。

最后写一下我在比赛写的垃圾的TLE代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e4+10;
int a,b,r;
pair<int,int>p[N];
#define x first
#define y second
 int n;
int check(int r)
{
    for(;r>0;--r)
   for(int i=0;i<n;++i)
    if(p[i].x/r!=p[i].y)
    return r;
    return 0;
}
 
int main()
{
   
    cin>>n; 
    int r=1e9+10;
    for (int i = 0; i < n; i ++ )
    {
        cin>>p[i].x>>p[i].y;
        r=min(r,p[i].x/p[i].y);
    }
    int l=check(r)+1;
    cout<<l<<" "<<r<<endl;
    return 0;
}

原文链接：https://blog.csdn.net/m0_70182646/article/details/130115548