CSUST OJ 1008 吃零食

吃零食"/>

CSUST OJ 1008 吃零食

吃零食

题意:桌上有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

思 路:这题一看就知道是贪心，选择贪心策略，按di从大到小排序，如果di一样大，则w从大到小排序。

收 获:排序型的贪心。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5+5;
struct node{int w,d,t;bool operator < (const node &p)const{if(d<p.d) return true;else if(d == p.d && w<p.w) return true;else return false;}
}a[maxn];
priority_queue<node> que;
int n;
int main(){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d %d",&a[i].w,&a[i].d);a[i].t = 0;que.push(a[i]);}ll sum = 0 ;int nowtime = 0;while(que.size()){node  p = que.top();que.pop();int num = p.w - (nowtime - p.t)*p.d;if(num <= 0){continue;}if(num < p.d){p.d = p.w = num;p.t = nowtime;que.push(p);continue;}sum+=num;nowtime++;}printf("%lld\n",sum);return 0;
}