作者：指针不指南吗
专栏：第14届蓝桥杯真题

🐾慢慢来，慢慢来🐾

题目

链接： 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≤10210^2102 。
对于 60% 的评测用例，1≤N≤10310^3103 。
对于 100% 的评测用例，1≤N≤10410^4104 ，1≤B≤A≤10910^9109 。

输入样例：

3
75 3
53 2
59 2

输出样例：

20 25

样例解释

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

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

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

代码摸索

第一次 AC 5/10

1. 用两个数组把 n 组 A、B存起来；

2. 在1~10510^5105 找到第一个满足条件的 V，即minV；

   在10510^5105 ~1找到第一个满足条件的 V，即maxV；

把数据范围 N 卡在 $10^5，是因为在 1~ N之间遍历判断的，如果 10910^9109 样例调用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;
}

反思

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

#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;
}

那么大的数据范围，就不应该去遍历，去尝试，应该直接二分

这个题是我后来自己做出来的，我哭死TvT

当时考的时候，还是太紧张了，有点手忙脚乱的感觉，没有写出来，确实没有很难

佳庆纺织