CSUST 1008 吃零食 题解（优先队列贪心）

题解（优先队列贪心）"/>

CSUST 1008 吃零食 题解（优先队列贪心）

题目链接

题目大意

题目思路

这个题目显然就是运用优先队列维护贪心，按di从大到小排序，如果di一样大，则w从大到小排序，但是要注意的是，如果num<p.d的时候要特判

代码

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define fi first
#define se second
#define debug printf(" I am here\n");
using namespace std;
typedef  long long ll;
typedef pair<int,int > pii;
const int maxn=1e6+5,inf=0x3f3f3f3f;
const double eps=1e-10;
int n;
struct node{//让消耗快的先取int w,d,t;friend bool operator<(node a,node b){if(a.d!=b.d){return a.d<b.d;}else{return a.w<b.w;}}
};
priority_queue<node> que;
signed main(){scanf("%d",&n);for(int i=1,w,d;i<=n;i++){scanf("%d%d",&w,&d);que.push({w,d,0});}ll sum=0;int now=0;while(!que.empty()){node q=que.top();que.pop();int num=q.w-(now-q.t)*q.d;if(num<=0){continue;}else if(num<q.d){//下一轮损失的不是q.d了，而是num,所以可以把这个//转化为下一秒损失q.d变为0的商品q.d=q.w=num;q.t=now;que.push(q);continue;}sum+=num;now++;}printf("%lld\n",sum);return 0;
}