关于这道题的正解
查看原帖
关于这道题的正解
461366
封禁用户楼主2022/8/2 19:43

我的算法是贪心,每一次选需求最大的人,结果只有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;
} 
2022/8/2 19:43
加载中...