有n个作业需要在一台机器上执行,一个时刻机器上只能执行一个作业,每个作业可在单位时间内完成,作业i有截止时间di,当作业i在截止时间被执行完,则可获得pi的收益。求最大收益。 第一行输入T(T<=10)表示有T组数据。每组数据先输入一个正整数N(1<=N<=50000),表示共有N个作业,随后输入N组(di,pi),表示每个作业的截止时间和收益。 输出T行正整数,第i行表示第i组数据下能获得的最大收益。写出c++实现代码
时间: 2024-02-28 09:54:21 浏览: 37
好的,下面是C++代码实现:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
struct Job {
int deadline, profit;
};
bool cmp(Job a, Job b) {
return a.deadline < b.deadline;
}
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
Job jobs[n];
for (int i = 0; i < n; i++) {
cin >> jobs[i].deadline >> jobs[i].profit;
}
sort(jobs, jobs + n, cmp); // 按照截止时间从小到大排序
int curTime = 0, totalProfit = 0;
for (int i = 0; i < n; i++) {
if (curTime + jobs[i].profit <= jobs[i].deadline) { // 执行该作业
curTime += jobs[i].profit;
totalProfit += jobs[i].profit;
}
}
cout << totalProfit << endl;
}
return 0;
}
```
代码思路就是按照上面的解题思路,先定义一个结构体Job来存储每个作业的截止时间和收益,然后按照截止时间从小到大排序,依次遍历每个作业,如果当前时间加上该作业执行时间不超过该作业的截止时间,则执行该作业,并将收益加入总收益中。最后输出总收益即为最大收益。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)