【Codeforces 767E】Change-free | Mrsrz's blog

贪心。

题目大意：

你有 $1145141919810$ 张百元大钞和 $m$ 枚一元硬币。

你要去买东西，共 $n$ 天。第 $i$ 天要花 $a_i$ 元钱，并且收银员找你 $1$ 元硬币，会增加 $w_i$ 的怒气值。当然找来的钱就归你了。

求一种付钱方案，使得收银员的总怒气值最小。输出方案。

题解：

这种套路题我思考时间有点长了啊

一个物品，要么付 $a_i\bmod 100$ 枚硬币，要么全付 $100$ 元的钞票，给他一枚硬币再让他找回来显然是劣的。

我们考虑先全部让他找钱，记录 $s_i$ 表示第 $i$ 天结束后你拥有的硬币。

然后我们考虑从第 $1$ 天开始，减少找钱的天数。

记录 $cost$ 表示当前已经花掉的硬币个数，那么第 $i$ 天剩余的硬币个数就是 $s_i-cost$。

如果剩下的钱够让这天不找零，那么我们就让他不找零，并将这天省下来的怒气值放入一个小根堆里。

如果剩下的钱不够让这天不找零，我们考虑让之前的一天变回找零，然后使得今天可以不用找零，并且使答案变优。

不难发现，从找零变成不找零，所需花费的硬币个数恰好相差 $100$，所以只需要把之前的 $1$ 人换下来就必然够。

那么显然是找增加的怒气值最小的那个换。取堆顶元素进行比较即可。

注意如果 $a_i\equiv 0\pmod{100}$，则它无论如何不会影响答案，可能需要特判。

时间复杂度 $O(n\log n)$。

Code：

#include<cstdio>
#include<queue>
using namespace std;
typedef long long LL;
const int N=1e5+5;
LL s[N],ans,cost;
int n,c[N],w[N],X[N];
bool vis[N];
struct data{
    int w,id;
    inline bool operator<(const data&rhs)const{return w>rhs.w;}
};
priority_queue<data>q;
int main(){
    scanf("%d%lld",&n,s);
    for(int i=1;i<=n;++i){
        scanf("%d",c+i);
        X[i]=c[i]/100,c[i]%=100;
    }
    for(int i=1;i<=n;++i)scanf("%d",w+i),w[i]*=(100-c[i])%100;
    for(int i=1;i<=n;++i)ans+=w[i],s[i]=s[i-1]+(100-c[i])%100;
    for(int i=1;i<=n;++i)if(c[i]){
        if(s[i]-cost>=100){
            cost+=100,ans-=w[i],vis[i]=1;
            q.push((data){w[i],i});
        }else if(!q.empty()&&q.top().w<w[i]){
            data u=q.top();q.pop();
            vis[u.id]=0,ans+=u.w-w[i],vis[i]=1;
            q.push((data){w[i],i});
        }
    }
    printf("%lld\n",ans);
    for(int i=1;i<=n;++i)if(vis[i]||!c[i])printf("%d %d\n",X[i],c[i]);else printf("%d 0\n",X[i]+1);
    return 0;
}