题目

链接： 4956. 冶炼金属 - AcWing题库

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

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

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

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

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

输入格式

第一行一个整数 N，表示冶炼记录的数目。

接下来输入 N 行，每行两个整数 A、B，含义如题目所述。

输出格式

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

数据范围

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

输入样例：
3
75 3
53 2
59 2
输出样例：
20 25
样例解释

当 V=20 时，有：[ $\frac{75}{20}$ ] =3，⌊ $\frac{53}{20}$ ⌋ =2，⌊ $\frac{59}{20}$ ⌋ =2，可以看到符合所有冶炼记录。

当 V=25 时，有：[ $\frac{75}{25}$ ] =3，⌊ $\frac{53}{25}$ ⌋ =2，⌊ $\frac{59}{25}$ ⌋ =2，可以看到符合所有冶炼记录。

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

代码摸索

第一次 AC 5/10

用两个数组把 n 组 A、B存起来；
在1~ $10^5$ 找到第一个满足条件的 V，即minV；

在 $10^5$ ~1找到第一个满足条件的 V，即maxV；

把数据范围 N 卡在 $10^5，是因为在 1~ N之间遍历判断的，如果 $10^9$ 样例调用famx地时候就会TLE ，更不行

每次遍历整个数据范围，O 很大，由这两点判断必须使用二分优化

#include<bits/stdc++.h>
using namespace std;const int N=1e5,M=1e4+10;int a[M]; //a存的是A
int b[M]; //b存的是Bint n; //q表示有几组数据//从小数到大数来寻找
int fmin(int a[],int b[])
{for(int i=1;i<N;i++)  //i表示转换率V{int flag=0;  //使用flag标志for(int j=0;j<n;j++)  //通过 j 来遍历数组中的元素{if(a[j]/i!=b[j])  flag=1; //只要有一个不满足就改变 flag 为1}if(flag==0) //全部满足，即找到所需要的，直接返回ireturn i;}
}//从大数往小数来寻找
int fmax(int a[],int b[])
{for(int i=N;i>=1;i--)  {int flag=0;for(int j=0;j<n;j++)  //数组{if(a[j]/i!=b[j])flag=1;}if(flag==0)return i;}
}int main()
{scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d",&a[i],&b[i]); //读入 n 组A,B}printf("%d %d",fmin(a,b),fmax(a,b)); //输出return 0;
}

第二次 AC 100%

二分优化

#include<bits/stdc++.h>
using namespace std;const int N=1e9,M=1e5+10;int a[M]; //a存的是A
int b[M]; //b存的是Bint n; //q表示有几组数据bool check1(int k)
{for(int j=0;j<n;j++)  //通过 j 来遍历数组中的元素{if(a[j]/k>b[j])return false;}return true;
}bool check2(int k)
{for(int j=0;j<n;j++)  //通过 j 来遍历数组中的元素{if(a[j]/k<b[j])return false;}return true;
}int main()
{scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d",&a[i],&b[i]);}int l=1,r=N;while(l<r){int mid=l+r>>1;if(check1(mid)) r=mid;else l=mid+1;}printf("%d ",l);l=1,r=N;while(l<r){int mid=l+r+1>>1;if(check2(mid)) l=mid;else r=mid-1;}printf("%d ",l);return 0;
}

反思

取下限，直接可以使用/做到
数组最大能开多大

#include<bits/stdc++.h>
using namespace std;
//在本人环境中
int c[20000][20000];
//全局数组能开到20000*20000int main()
{int b[100][100];	        // 函数中二维数组最大能开100*100char a[4* 518028];// 函数中的char数组最大能开4*518028int b1[500000];  // int最大能开到518028 return  0;
}