洛谷P6155 修改题解

题意：

给定一个长度为 \(n\) 的整数序列 \(a_i\)，再给定一个长度为 \(n\) 的整数序列 \(b_i\)。

你可以进行一些修改，每次你可以将一个 \(a_i\) 增加 \(1\)，花费为 \(b_i\)，你需要使所有的 \(a_i\) 不相等，且同时满足花费最少。

但 zbw 认为太过简单，于是他规定，你可以在修改前进行无限次如下操作：交换 \(b_i,b_j(1 \leq i,j \leq n)\)。

求最小的花费。

由于答案可能很大，请输出答案对 \(2^{64}\) 取模后的值。

输入格式：

第一行一个整数 \(n\)。

第二行 \(n\) 个整数，第 \(i\) 个数表示 \(a_i\)。

第三行 \(n\) 个整数，第 \(i\) 个数表示 \(b_i\)。

输出格式：

输出一行一个整数，表示答案对 \(2^{64}\) 取模的值。

数据范围：

对于所有数据 \(1 \leq n \leq 10^6\)，\(1\leq a_i,b_i\leq10^9\)。

这里的无限次交换其实就是随便顺序

贪心地想，对修改次数越多的花越小的 \(b_i\) 一定是最优的。

然后考虑怎么修改

容易想到先把 \(a_i\) 顺序排序，然后遇到相等的就让后面所有的都加一

然后你会发现过不了样例二。

因为你把一个修改分给了两个人，显然会花费更多。

也就是只要把重复的那个提升到最近的空位即可。

这个最近的空位怎么求呢？我们可以用并查集来维护

对于每个数 \(x\) ，记一个 \(f_x\) 表示它的下一个空位。

我们从小到大依次处理每个 \(x\) 的 \(f_x\)

如果 \(f_x\) 还没有值，就让它为 \(x+1\) ，即 \(f_x \gets x+1\)

如果它已经有值了，说明 \(f_x\) 已经被填了

于是我们找 \(f_x\) 的下一个空位是谁，即 \(f_x \gets f_{f_x}\) ，显然这个可以路径压缩

unordered_map<int,int> f;
int find(int x)
{
    if(!f[x]) return f[x] = x+1;
    return f[x] = find(f[x]);
}

总时间复杂度 \(O(n \log n)\)

注意答案要对 \(2^{64}\) 取模（其实就是unsigned long long自然溢出）

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(1e6+15))

int n,a[N],b[N];
unsigned int ans;
unordered_map<int,int> f;
vector<int> v;
int find(int x)
{
    if(!f[x]) return f[x] = x+1;
    return f[x] = find(f[x]);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n);
    for(int i=1; i<=n; i++) read(a[i]); sort(a+1,a+1+n);
    for(int i=1; i<=n; i++) read(b[i]); sort(b+1,b+1+n);
    for(int i=n,x; i; i--)
    {
        x=find(a[i]) - a[i] - 1;
        if(x) v.push_back(x);
    }
    sort(v.begin(), v.end(),greater<int>());
    for(int i=0,x=1; i<v.size(); i++)
        ans += (unsigned int)v[i] * b[x++];
    printf("%llu\n",ans);
    return 0;
}