source： CodeForces - 767E
题意：只有面值为100的纸币和1元的硬币，现纸币无限多，但只有 m 个一元硬币，给出接下来的 n 天去食堂每天花费 的钱数：c[i] 元。已知收银员在第 i 天找零 x 元的话，不满意度会增加 w[i]，求最小不满意度。
思路：从贪心的角度理解，我们首先是尽可能地每天都用硬币支付，直到某一天发现手里的硬币为负值了，说明前面一定有一天需要用纸币换取硬币，那么贪心的想法就是既然不论选哪一天都是相当于多了100个硬币（效果是一样的），只需找到选择哪一天不满意度最小即可，于是可以想到用优先队列来做！
注意：
1. 优先队列的使用见： UVA 11995 I Can Guess the Data Structure!【栈+队列+优先队列基本用法】
有必要强调的是优先队列比较标准：写的>，但排序结果正好相反是小的在在顶端！ 2. 若某一天正好花钱数是100的整数倍，不用将它push入优先队列
代码如下：
#include<cstdio> #include<queue> using namespace std; const int max_n=100005; int c[max_n],w[max_n],ans[max_n][3]; struct cmp { bool operator()(int a,int b) { return w[a]*(100-c[a]0)>w[b]*(100-c[b]0); //注意这里比较标准写的>，但排序结果正好相反是小的在在顶端 } }; priority_queue<int,vector<int>,cmp> q; int main() { long long n,m,sum=0; scanf("%lld%lld",&n,&m); for(int i=0;i<n;i++) scanf("%d",&c[i]); for(int i=0;i<n;i++) scanf("%d",&w[i]); for(int i=0;i<n;i++) { int r=c[i]0; ans[i][0]=c[i]/100; ans[i][1]=r; m-=r; if(r!=0) //若为100的整数倍，不能压入优先队列，因为它不存在找零问题 { q.push(i); if(m<0) { int t=q.top(); ans[t][0]++; ans[t][1]=0; m+=100; sum+=w[t]*(100-c[t]0); q.pop(); } } } printf("%lld\n",sum); for(int i=0;i<n;i++) printf("%d %d\n",ans[i][0],ans[i][1]); return 0; }
