[数据结构与算法]Gym102916K. Bloodseeker 贪心

Link
贪心

题意

一个吸血鬼 有$m$ 滴血的上限，一开始满血，每秒钟会掉一滴血，且可以对一个怪物造成1点伤害,有 $n$个 怪物，每个怪物有 $t_i$滴血，击杀一个怪物后可以回复 $h_i$ 滴血，但是不能超过上限，问是否可以击杀所有怪物

思路

首先由于恢复体力后体力也不能超过上限，所以预处理 $h_i=min(m,h_i)$
1.由于可以更改攻击目标，所以若 $h_i\ge t_i$，则可以回复 $h_i?t_i$ 点血量
2.若 $h_i<t_i$，考虑 $ij$ 两个怪物先后杀的顺序，会导致最低的血量不同，写一下式子，发现先杀回复量大的怪即可，所以按照 $h_i$ 从大到小排序。

代码

int n, m;
struct Node {
	int t, h;
	/*
	bool operator < (const Node &x) const {
		if(h-t>0 &&  (x.h-x.t) <= 0)
			return 1;
		if(h-t>0 && (x.h-x.t)>0)
			return t < x.t;
		return h > x.h;
	}
	*/
	bool operator < (const Node &x) const {
		return h > x.h;
	}
}node[maxn];
void solve() {
    cin >> n >> m;
    int q = m;
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
    	int t, h;
    	cin >> t >> h;
    	h = min(h, m);
    	if(h - t > 0) {
    		q += h - t;
    	}
    	else {
    		node[++cnt] = (Node){t, h};
    	}
    }
    sort(node + 1, node + cnt + 1);
    for(int i = 1; i <= cnt; i++) {
    	// cout << node[i].t << ' ' << node[i].h << endl;
    	if(q < node[i].t) {
    		cout << "NO\n";
    		return;
    	}
    	q -= node[i].t - node[i].h;
    }
    cout << "YES\n";
}