T3-修改

· · 题解

一道很水的贪心题，由于太水了，就直接对正解进行讲解。

首先，如果没有 b_i 的限制。我们可以用一个队列，枚举每个位置，如果这个位置上有点，则将这个位置的所有 a_i 加入。然后，将一个 a_i 放在这个位置。

举个例子。

假如有 2,2,3 三个点：

枚举位置 1，没有点。

枚举位置 2，将两个 2 加入队列，将一个 2 弹出。

枚举位置 3，将 3 加入队列，将另一个 2 弹出。

枚举位置 4，将 3 弹出。

每个点被修改的次数即为 出队时间 - 入队时间。然后按修改的次数排序再乘上 b_i 即可。

但有时有多种选择，比如在上述样例中，时间 3 时，既可以弹出 2 又可以弹出 3 ，但弹出 2 肯定是更优的，因为 2 的入队时间比 3 靠前，乘上的 b_i 一定比 3 少，所以多修改一次 2 的代价更小。

所以将上述的队列改为栈。

但时间复杂度还是 O(n\log n+\max a_i) 的。

但可以发现，其实很多时候栈都是空的，优化就是在栈为空的时候跳到下一个 a_i。

可以证明栈有值的点至多有 2n 个。

总复杂度 O(n\log n) (排序)。

#pragma GCC optimize(2,3,4,5)
#include<bits/stdc++.h>
#define re register
using namespace std;
struct node{
    int x,id;
};
struct d{
    int ans,pos;
}p[1000002];
int n,a[1000002],b[1000002],x,l;
unsigned long long ans;
inline int read(){
    int t=0;
    char v=getchar();
    while(v<'0')v=getchar();
    while(v>='0'){
        t=(t<<3)+(t<<1)+v-48;
        v=getchar();
    }
    return t;
}
inline bool cmp(re d x,re d y){
    return x.ans>y.ans;
}
stack <node> q;
signed main(){
    n=read();
    for(re int i=1;i<=n;++i)a[i]=read();
    sort(a+1,a+n+1);
    for(re int i=1;i<=n;++i)b[i]=read();
    sort(b+1,b+n+1);
    l=1;
    x=1;
    while(1){
        if(q.empty()){
            if(l<=n)
            x=a[l];
            else break;
        }
        while(a[l]==x){
            q.push(node{a[l],l});
            ++l;
        }
        node tmp=q.top();
        q.pop();
        p[tmp.id].ans=x-tmp.x;
        ++x;
    }
    sort(p+1,p+n+1,cmp);
    for(re int i=1;i<=n;++i){ans+=1llu*p[i].ans*b[i];
    }
    printf("%llu",ans);
}