杭电多校 故障机器人想活下去 优先队列+贪心

原题：CAUC-OJ-故障机器人想活下去、 HDOJ-故障机器人想活下去

参考思路：CSDN博客

总结：按序列依次受伤害、减生命值，并同时将伤害序列推入优先队列。当生命值为负值时，进行循环：对当前伤害序列中伤害值最大的那次伤害使用烟雾弹（改写历史），并重新加回对应的生命值，直至：生命值大于零，或烟雾弹不够，或优先队列排空。若循环后生命值仍小于零，则输出i，表示除当前回合的前i回合可存活，本回合不可存活。若上述过程结束机器人的生命值仍为正，则输出总敌人数n。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+1;
int a[N], b[N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while(t--) {
		int n,x,k;
		cin >> n >> x >> k;		
		for (int i = 0; i < n; ++ i) {
			cin >> b[i];
			a[i] = b[i];
		}
		if (k >= n) {
			cout << n << endl;
			continue;
		}
		priority_queue <int> q;
		int f = 0;
		for (int i = 0; i < n; ++ i) {
			q.push(b[i]);
			x -= a[i];
			if (x <= 0 && k > 0) {
				while (x <= 0 && k > 0 && !q.empty()) {
					x += q.top();
					q.pop();
					k--;
				}
			}
			if (x <= 0) {
				f = 1;
				cout << i << endl;
				break;
			}
		}
		if (!f) {
			cout << n << endl;
		}
	}
	return 0;
}
// 1  1  2  3  4  4  6 9 10 12
// 19 18 16 13 9  5        
// 6  12  9 4  10 1 3 4 2 1
// 14 --  - 10 -- 9 6 2