现有n个任务,要交给A和B完成。每个任务给A或给B完成,所需的时间分别为ai和bi。问他们完成所有的任务至少要多少时间。第一行一个正整数n,表示有n个任务。接下来有n行,每行两个正整数ai,bi。一个数,他们完成所有的任务至少要的时间。1 <= n <= 200 , 1 <= ai,bi <=200(代码,语言c++)
时间: 2023-12-03 14:46:31 浏览: 189
以下是C++的代码实现:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 205;
int n, a[MAXN], b[MAXN];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
sort(a+1, a+n+1); // 按照完成任务所需时间从小到大排序
sort(b+1, b+n+1);
int ans = max(a[1], b[1]); // A和B中完成第一个任务所需时间的最大值
for (int i = 2; i <= n; i++) {
ans += min(max(a[i], b[i-1]), max(a[i-1], b[i])); // 选择A或B中完成任务所需时间较小的那个
}
cout << ans << endl;
return 0;
}
```
具体思路:
首先将完成每个任务所需时间的两个数组分别按照从小到大排序。
接下来,分别比较A和B完成第一个任务所需时间,取其中的最大值作为总时间的初始值。
之后,从第二个任务开始,每次比较A和B完成当前任务所需时间的大小,选择其中较小的那个,累加到总时间中。
最后输出总时间即可。
时间复杂度为$O(nlogn)$。
阅读全文