米尔科和斯拉夫科正在打一场新的比赛。再一次斯拉夫科在每一轮比赛开始时都会给米尔科两个数字A和B,两个数字都小于100。米尔科随后必须为斯拉夫科解决以下任务:如何将所有给定的A数与所有给定的B数配对,以便这些配对的最大和尽可能小。 换句话说,如果在前几轮比赛中斯拉夫科给出了a1,a2,a3…an和b1,b2,b3…bn,确定n对(ai,bj),使所有和ai+bj的最大值最小。给出思路和C++代码
时间: 2024-03-16 10:42:38 浏览: 326
这是一道经典的二分答案问题,可以使用二分法解决。具体实现步骤如下:
1. 定义左右边界,初始时左边界为0,右边界为200(100+100),即ai+bj的最大值不会超过这个范围。
2. 计算中间位置mid,mid = (left + right) / 2。
3. 假设当前mid是满足条件的最小和,遍历所有的A数和B数,找到一组Ai和Bj,使得Ai + Bj > mid。
4. 如果找到了这样的一组Ai和Bj,则说明mid太小,将左边界移动到mid+1。
5. 如果没有找到这样的一组Ai和Bj,则说明mid可以作为满足条件的和,将右边界移动到mid-1。
6. 重复步骤2-5,直到左右边界重合。
根据上述步骤,我们可以得到如下C++代码实现:
```c++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
}
int left = 0, right = 200, ans = 0;
while (left <= right) {
int mid = (left + right) / 2;
bool flag = false;
for (int i = 0; i < n; i++) {
if (a[i] + b[i] > mid) {
flag = true;
break;
}
}
if (flag) {
left = mid + 1;
} else {
right = mid - 1;
ans = mid;
}
}
cout << ans << endl;
return 0;
}
```
在上述代码中,我们使用了一个bool类型的flag变量来判断当前mid是否满足条件。如果找到了一组Ai和Bj,使得Ai + Bj > mid,则将flag设为true,否则flag为false。在遍历完所有的A数和B数后,如果flag为false,则说明当前mid是满足条件的最小和,将ans更新为mid。最后输出最小和即可。
阅读全文