吃零食 贪心

贪心"/>

吃零食 贪心

描述：

吃零食

桌上有n袋零食，不同的零食会有不同的美味程度wi和腐坏程度di，每种零食在一单位时间内美味程度都会下降di，但是不会降到0以下。

qwb每一单位时间可以吃掉一袋零食。现在qwb想要在吃完所有零食后获得的美味度最大。问最大值是多少？

输入：

第一行,一个整数n，代表有n袋零食接下来n行，每行2个整数wi和di(1<=n<=100,000)，(0<=wi<=1,000,000,000)，(0<=di<=10,000)

输出：

输出一行，最大的美味度。

样例输入：

4
5 3
4 3
5 4
7 5

样例输出：

9

题解：

贪心策略就是先吃腐烂最快的，在美味度很大的时候，腐烂值等于美味度的减少值。

但是在最后一次，食物即将腐烂的时候，美味度的减少值 <= 腐烂值 ，所以我们这时候，用前一天食物剩下的美味度更新食物的腐烂度和总美味度。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 100010;
struct Node {int d, w, t;bool operator<(const Node& rhs) const {//priority_queueif (d == rhs.d)return w < rhs.w;return d < rhs.d;//贪心策略是先吃腐烂最快的，比如说如果不会腐烂， }//那么所吃的总美味度是sum，腐烂一次，总美味度减d总，
};//但是你把腐烂最快的吃了，总美味度减（d总-吃的腐烂度），所以要先吃腐烂最快的
priority_queue<Node> pq;//我们用优先队列维护腐烂最快的数组
int main(void) {int n, day = 0;long long ans=0;Node temp;cin >> n;for (int i = 1; i <= n; i++) {cin >> temp.w >> temp.d;temp.t = 0;pq.push(temp);}while (!pq.empty()) {temp = pq.top();pq.pop();int num = temp.w - temp.d * (day - temp.t);//所能获得的美味度if (num <= 0)//小于0代表已经腐烂，等于0代表没腐烂，但吃了获得不了美味度continue;else if (num < temp.d) {//所能获得的美味度已经小于该食物的腐烂值，我们此时要改变贪心策略，因为以前我们是基于temp.t = day;//食物的腐烂度等于美味度的损失进行贪心的，但是现在腐烂度不等于美味度的损失了。temp.w = temp.d = num;//我们强行让腐烂度等于美味度的损失pq.push(temp);continue;}ans += num;day++;}cout << ans << endl;return 0;
}