我的算法是贪心,每一次选需求最大的人,结果只有20pts。是我写挂了还是思路有问题?
如果您有HACK,请at我并且留下您的HACK,感激不尽。
#include <bits/stdc++.h>
using namespace std;
struct node {
int time, id, rest;
// time: 需要休息的时间
// id: 编号
// rest: 从多少秒开始休息
} a[1000]; // 乐队
bool cmp_time(node x, node y) {
// 按照需要休息的时间排序
return x.time > y.time;
}
bool cmp_id(node x, node y) {
// 按照编号排序
return x.id < y.id;
}
int main() {
int t, n;
cin >> t >> n;
for (int i = 0; i < n; i++) cin >> a[i].time;
for (int i = 0; i < n; i++) a[i].id = i; // 初始化编号
sort(a, a + n, cmp_time); // 贪心地按照需求排序
int j = 0;
int cnta = 1, cntb = 1;
for (int i = 0; i < t; i++) {
if ((--cnta) == 0) {
cnta = a[j].time;
a[j].rest = i;
j++;
}
if (j == n) break;
if ((--cntb) == 0) {
cntb = a[j].time;
a[j].rest = i;
j++;
}
if (j == n) break;
}
sort(a, a + n, cmp_id); // 重新按照编号排序
for (int i = 0; i < n; i++) cout << a[i].rest << " "; // 输出答案
return 0;
}