上海计算机学会2024年9月月赛C++乙组T1加热午餐
发布时间
阅读量：
阅读量
加热午餐
内存限制: 256 Mb时间限制: 1000 ms
题目描述
n 个人要在一台微波炉上加热他们的午餐。其中每个参与者i在使用微波炉时需花费的时间为ai分钟。每台微波炉仅能同时处理一份食物。一旦完成了 lunch 的 heating process（即所有 participants 完成他们的 ai minutes），每个参与者i 将立即开始用餐。每个 participant i 在吃完他们的 lunch 方面耗时 bi minutes。
为了使大家尽快地吃完午餐，请问这些人应该排着队使用唯一的一个微波炉按照什么顺序？
输出最后一个人吃完午餐的最早时间。
输入格式
- 第一行：单个整数表示 n
- 第二行到第 n+1 行：第 i+1 行两个整数表示 ai 与 bi。
输出格式
- 单个整数：表示答案
数据范围
- 30% 的分数，1≤n≤10
- 60% 的分数，1≤n≤100
- 100% 的分数，1≤n≤100,000
- 1≤ai≤20,000
- 1≤bi≤100,000,000
样例数据
输入:
3
2 2
2 7
3 4
输出:
9
说明:
先安排2 7，然后是3 4，最后是2 2
解析：核心是如何安排热饭的顺序
详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
struct node {
int a, b;
};
node a[100005];
long long ta = 0, tb = 0;
bool cmp(node x, node y) { //排序，b大的排前面
return x.b > y.b;
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i].a >> a[i].b;
}
sort(a + 1, a + n + 1, cmp);
for(int i = 1; i <= n; i++) { //计算时间
ta += a[i].a;
tb = max(ta + a[i].b, tb);
}
cout << tb;
return 0;
}全部评论 (0)
还没有任何评论哟~