Codeforces Round #398 (Div. 2) E. Change-free 贪心 优先队列

题意：你有无数的面值为100的纸钞和m个硬币。收银员有无数的纸钞和硬币，但是他不爱找钱。收银员在第i天有愤怒值wi，若收银员找纸钞和硬币的总个数为x，则这一天他的愤怒程度为x*wi，给定你每天要花钱的数目，以及起始时手里的硬币，要求输出n天来收银员的最小总愤怒程度以及每天给收银员纸币与硬币的个数。

解法：分析下样例并且稍加思考可以发现，多给纸钞是无意义的，所以每天的状态无非就是：

1.把硬币给齐；

2.多给一张纸钞令其找钱。

这两种方案刚好相差100个硬币，即如果我们要反悔，即要改变之前某一天的策略，从“给齐硬币”->“给定纸钞令收银员找钱”，则等价于：手里的硬币增加了100个，并会增加当天收银员找钱的愤怒值wi*x这么多的代价。

故我们可以按天数扫过一遍，有硬币的时候就直接给钱，并将反悔方案存到优先队列（最小堆）里面，在不得不令收银员找钱的时候，弹出优先队列的队首，即最值得反悔的那一天，让收银员找钱。

下面是代码：

#include <cstdio>#include <queue>using namespace std;#define fst first#define snd secondconst int maxn=1e5+5;typedef long long ll;typedef pair<ll,int> pli;int n;ll m,c[maxn],w[maxn],res,ca[maxn];bool vis[maxn];PRiority_queue<pli,vector<pli>,greater<pli> > que;int main(){    scanf("%d%lld",&n,&m);    for (int i=1;i<=n;++i)        scanf("%lld",&c[i]);    for (int i=1;i<=n;++i)        scanf("%lld",&w[i]);    for (int i=1;i<=n;++i) {        ca[i]=c[i]/100;        c[i]%=100;        if (!c[i])            continue;        que.push(pli(w[i]*(100-c[i]),i));        m-=c[i];        if (m<0) {            res+=que.top().fst;            vis[que.top().snd]=true;            m+=100;            que.pop();        }    }    printf("%lld/n",res);    for (int i=1;i<=n;++i)        if (vis[i])            printf("%lld 0/n",ca[i]+1);        else            printf("%lld %lld/n",ca[i],c[i]);    return 0;}