[蓝桥杯]真题解说：冶炼金属（暴力+二分）

一、视频解说

视频解说

二、暴力代码

1. //暴力代码
2. #include<bits/stdc++.h>
3. #define endl '\n'
4. #define deb(x) cout << #x << " = " << x << '\n';
5. #define INF 0x3f3f3f3f
6. using namespace std;
7. const int N = 1e4 + 10;
9. void solve()
10. {
11.         int n; cin >> n;
12.         vector<int>a(n), b(n);//创建数组
13.         for(int i = 0; i < n; i ++)
14.                 cin >> a[i] >> b[i];
16.         for(int i = 1; i <= 1e6; i ++)//枚举的转化率V
17.         {
18.                 bool flag = true;//标记一下当前的V是否合法
20.                 for(int j = 0; j < n; j ++)
21.                 {
22.                         if(b[j] != (a[j] / i))
23.                         {
24.                                 flag = false;
25.                                 break;
26.                         }
27.                 }
28.                 if(flag)
29.                 {
30.                         cout << i << " ";
31.                         break;
32.                 }
33.         }
34.        
35.         for(int i = 1e6; i >= 1; i --)
36.         {
37.                 bool flag = true;
38.                 for(int j = 0; j < n; j ++)
39.                 {
40.                         if(b[j] != (a[j] / i))
41.                         {
42.                                 flag = false;
43.                                 break;
44.                         }
45.                 }
46.                 if(flag)
47.                 {
48.                         cout << i << " ";
49.                         break;
50.                 }
51.         }
53.        
54. }
56. signed main()
57. {
58.         ios::sync_with_stdio(0);
59.         cin.tie(0);
60.         cout.tie(0);
61.         int t;
62.         t = 1;
63.         //cin >> t;
64.         while(t--)
65.         solve();
66. }

复制代码

三、正解代码

1. //冶炼金属：二分
2. #include<bits/stdc++.h>
3. #define int long long
4. using namespace std;
5. const int N = 1e4 + 10;
6. int a[N], b[N];
7. int n;
9. bool check_min(int mid)
10. {
11.         for(int i = 0; i < n; i ++)
12.         {
13.                 if(b[i] < a[i] / mid)
14.                         return false;
15.         }
17.         return true;
18. }
20. bool check_max(int mid)
21. {
22.         for(int i = 0; i < n; i ++)
23.                 if(b[i] > a[i] / mid)
24.                         return false;
26.         return true;
27. }
29. void solve()
30. {
31.         cin >> n;
32.         for(int i = 0; i < n; i ++)
33.                 cin >> a[i] >> b[i];
35.         //求最小值。
36.         int lmin = 1, rmin = 1e9;
37.        
38.         while(lmin < rmin)
39.         {
40.                 int mid = lmin + rmin >> 1;
41.                 if(check_min(mid))
42.                         rmin = mid;
43.                 else
44.                         lmin = mid + 1;
45.         }
47.         //求最大值。
48.         int lmax = 1, rmax = 1e9;
49.         while(lmax < rmax)
50.         {
51.                 int mid = lmax + rmax + 1 >> 1;
52.                 if(check_max(mid))
53.                         lmax = mid;
54.                 else
55.                         rmax = mid - 1;
56.         }
58.         cout << lmin << " " << lmax << endl;
59. }
61. signed main()
62. {
63.         ios::sync_with_stdio(0);
64.         int t = 1;
65.         // cin >> t;
66.         while(t--)
67.         solve();
68. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。