CF767E-Change-free
题目大意
你接下来n nn天回去食堂吃饭，而且现在你已经决定好了吃什么，所以你在接下来的第i ii天，花费c i c_ici元。
交易时只允许使用1 11元的硬币和100 100100元的纸币，你初始有m mm硬币和无限多的纸币。在其中的某些天你可能不够正好支付c i c_ici元，所以会面临找零。但是收银员在找零时会产生不满。如果收银员在第i ii天找了x xx纸币和硬币。那么会产生x ⋅ w i x \cdot w_ix⋅wi点不满。收银员总是尽量用最少的硬币和纸币找零。
你希望使得收银员总不满尽可能小。你需要确认在接下来n nn天的最小总不满和如何支付的方案。
题解
考虑贪心，现在手上有的硬币如果满足当天所需，则尽可能使用。否则就找到在此之前不满程度最小的一天，来找零。对于被找零的那天，本身花了c i % 100 c_i \% 100ci%100元，现在不仅没花，而且获得了100 − c i % 100 100-c_i \% 100100−ci%100元，所以一次找零的贡献是固定的100 100100。因此对于每一天来说都有一个固定的不满，和一样的贡献。所以用优先队列维护不满最小值。每次取最小值即可。
#include<bits/stdc++.h>#defineiosios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#defineumapunordered_map#defineendl'\n'usingnamespacestd;usingi128=__int128;constintmod=1e9+7;template<typenameT>voidread(T&x){x=0;intf=1;charc=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;}template<typenameT>voidprint(T x){if(x<0){putchar('-');x=-x;}if(x>9)print(x/10);putchar(x%10+'0');}#defineintlonglongconstintN=500005;constintM=2000005;map<int,int>ans;inlinevoidsolve(){ans.clear();intn,m;cin>>n>>m;vector<int>num(n+1);for(inti=1;i<=n;i++){cin>>num[i];}vector<int>w(n+1);for(inti=1;i<=n;i++)cin>>w[i];priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;intcost=0;for(inti=1;i<=n;i++){if(num[i]%100==0)continue;q.push({(100-(num[i]%100))*w[i],i});if(m<num[i]%100){m+=100;cost+=q.top().first;ans[q.top().second]++;q.pop();}m-=num[i]%100;// cout<<m<<endl;}cout<<cost<<endl;for(inti=1;i<=n;i++){if(ans[i]){cout<<num[i]/100+1<<" "<<0<<endl;}else{cout<<num[i]/100<<" "<<num[i]%100<<endl;}}}signedmain(){ios;intT=1;// cin>>T;for(;T--;)solve();return0;}
