P6155题解
闲话
这是本蒟蒻写的第三篇题解了，前两篇都因为种种原因报废了，求管理过╥﹏╥
正片
大家好，我是一名STL选手，于是我用了大量STL+O2的代码过了这道题
分析
我的代码与目前题解区的思路有所不同，会在理解和实现方面有差异，但本质好像神似（？
看到题目，脑子里一定有一个思路，就是我让操作次数最多的a[i]配对上最大的b[i]，这样一定最优
既然有大小之分，那一定要排序了，值域1e9，复杂度上界是死死的$O(nlogn)$你要是会基数排序那另说,我们作为一个STL选手，接下来就可以在这个基础上推 (luan) 理 (gao) 了
问题的瓶颈在如何找到一个合适的a数组的处理方案，我们可以发现，当处理完后的a数组的最大值最小的时候，一定最优，因为处理后的数组是由原数组变过来的，而我们可以进行的操作又只有 +1 这一种，因此最大值最小的时候进行的操作最少，所以我们有了一个大方向
再想想，什么时候其最大值能最小呢? 我们观察一下这个要求，要求数组内的数据没有重复的，且只能向上加，那我们就有了一个很朴素的想法————取光所有数值间的空隙值
这篇题解若这么写下去就和其他的没啥不同了，所以我们换一种思路从一种错误的思路导出正解
我在一开始想的是，我们排序a数组，正着扫，对于相同的数，第一个不变，后面的 +1 ，维护一个前面的最大值，若扫到的数小于最大值，就暴力加上去
然而这个思路是错的，具体原因请见样例 2
我们又想了，为什么这个是错的呢？因为一个数的修改可能带动后面很多数的修改，而就像样例 2 一样，有些元素可以先不修改，等到后面再修改，这样我们就有了第二种思路，把重复的元素放到一边，到后面再修改，结合上面的分析，我们觉得应该有空位就插进去，没空位就扔一边，以及有一个空位多个后放的数时，优先放最近的 ( 后面这个一会儿再证
这个思路其实就是正解了，但我们接下来说明一下其对于上一种错解的好好在哪里
首先，我们要证明，将任意一个数后放都是比将其抬高不劣的
我们发现，一个数后放的地方有一定规律，就是在原数位置和后放位置之间的这一段数列，是递增的公差为1的等差数列
为啥呢？由于我们排了序，所以一定是递增的，因为我们在有空隙的时候先插最近的，所以一定是等差的
那么我们对比一下，我们设中间这一段的长度为 len ，那后放的代价是 len+1 ,抬高的代价最好也是 len+1 （当中间这一段都没有重复元素的时候）
看起来两者最好的时候都一样，那是不是可以证明其不劣了？
当然可以，但我们闲的淡疼可以再证明错解最好时也是劣的(结尾空隙大特判不算)，我们注意到后放的代价是直接加到一个节点的，而抬高则是平摊在各个元素中的，我们在配对的时候可以发现总代价相同的时候，第一种总是不劣的，所以后放就完成了对抬高的吊打
我们再证一下第二条选择规定，在有多个元素的时候，其实我们无论选哪个，总代价都是相同的，但就像我们上面所说一样，集中一定比分散好，所以我们选最近的，让更远的分摊更大的代价
综上，我们完成了证明
code
这里就可以上代码了，我们先统计每一个数出现了多少次，然后排序去重，从小到大枚举，有空就插，没空就后放，最后对 b 进行一次排序，匹配
代码里的优先级队列可以换成普通队列，因为数已经排过序了
此份代码不吸氧只有30pts，但吸了氧能过
//#pragma GCC optimize(2)
#include <iostream>
#define ull unsigned long long
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <vector>
using namespace std;
const int maxN= 1e6+10;
int b[maxN],cost[maxN],n,temp,idx;
vector<int> a;
ull ans=0;
unordered_map<int,int> mp;
priority_queue<int,vector<int>,less<int> >q;
bool comp(int x,int y){
return x>y;
}
signed main(){
//freopen("test.in","r",stdin);
ios::sync_with_stdio(false);//cin加速
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);//再度加速
//不能用printf,scanf
cin >> n ;
for(int i=1;i<=n;++i)
cin >> temp,a.push_back(temp), mp[temp]++;
for(int i=1;i<=n;++i)
cin >> b[i];
a.push_back(0x7ffffff);
sort(a.begin(),a.end());
// for(int x:a){
// cout << x << ' ';
// }cout << endl;
int n=unique(a.begin(),a.end())-a.begin(),maxn=0;
//a[n+1]=0x7ffffff;
// cout << n << endl;
for(int i=0;i<n-1;++i){
maxn=max(maxn,a[i]);
mp[a[i]]--;
cost[++idx]=0;
int p=1;
while(mp[a[i]]&&(a[i]+p<a[i+1])){
cost[++idx]=p;
maxn=max(maxn,a[i]+p);
++p,--mp[a[i]];
}
if(mp[a[i]]){
while(mp[a[i]]--) q.push(a[i]);
}
else{
while(a[i]+p<a[i+1]&&!q.empty()){
cost[++idx]=a[i]+p-q.top();
q.pop();
p++;
}
}
// cout << cost[i] << endl;
}
//cout << idx << endl;
//cout << maxn <<
sort(cost+1,cost+idx+1);
sort(b+1,b+idx+1,comp);
//for(int i=1;i<=idx;++i)
// cout << cost[i] << " ";
//cout << endl;
for(int i=1;i<=idx;++i)
ans+=(ull)b[i]*(ull)cost[i];
cout << ans << '\n';
return 114514-114514;
}