题意：
给你n组数，每组数有a和b两个数，代表数量和让数量加1的花费，问让所有数量都不相同的最小代价。
思路：
先按照数量从小到大排序，因为只能进行+ 1的操作；对于相同数量的再按照花费从小到大排序。
优先队列里维护相同数量的数+ 1的总花费。
如果目前数量发生了变化，就枚举优先队列的数跟两个数量之间的差值。每次都让最大的保留，将其他的花费加到a n s里。这样有两种情况：要么两个数量之间的差值小于优先队列的数的个数，要么大于等于。对于前者，一定是最优的；对于后者，再继续将当前数量的数加入优先队列，重复上述操作，也是最优的。
还有一种写法就是按照花费从大到小排序，相同花费再按照数量从小到大排序。这样排序是因为，花费多的我们肯定想少操作。然后用并查集维护数量未到达过的值，将当前节点和+ 1节点合并，表示+ 1,计算贡献的时候就是花费*差值。
代码:
优先队列思路
// Problem: A. Recommendations // Contest: Codeforces - VK Cup 2019-2020 - Elimination Round (Engine) // URL: https://codeforces.com/problemset/problem/1310/A // Memory Limit: 512 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=2e5+100; int n; struct node{ ll val,w; }; node a[maxn]; bool cmp(node a,node b){ return a.val<b.val; if(a.val==b.val) return a.w<b.w; } int main(){ n=read; rep(i,1,n) a[i].val=read; rep(i,1,n) a[i].w=read; sort(a+1,a+1+n,cmp); priority_queue<ll>q; ll ans=0,sum=0; //rep(i,1,n){ /// cout<<a[i].val<<"++++"<<a[i].w<<endl; //} for(int i=1;i<=n;i++){ if(a[i].val==a[i-1].val){ sum=sum+a[i].w; q.push(a[i].w); } else{ for(int j=a[i-1].val;j<a[i].val&&!q.empty();j++){ sum=sum-q.top(); q.pop(); ans=ans+sum; } sum+=a[i].w; q.push(a[i].w); } //cout<<sum<<" "<<ans<<endl; } while(!q.empty()){ sum=sum-q.top(); q.pop(); ans=ans+sum; } printf("%lld\n",ans); return 0; }
并查集思路
// Problem: A. Recommendations // Contest: Codeforces - VK Cup 2019-2020 - Elimination Round (Engine) // URL: https://codeforces.com/problemset/problem/1310/A // Memory Limit: 512 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=2e5+100; int n; struct node{ ll val,w; }; node a[maxn]; bool cmp(node a,node b){ if(a.w==b.w) return a.val<b.val; return a.w>b.w; } map<int,int>root; int Find(int x){ if(!root.count(x)) return x; if(x!=root[x]) root[x]=Find(root[x]); return root[x]; } void Union(int x,int y){ int fx=Find(x),fy=Find(y); if(fx!=fy) root[fx]=fy; } int main(){ n=read; rep(i,1,n) a[i].val=read; rep(i,1,n) a[i].w=read; sort(a+1,a+1+n,cmp); ll ans=0; for(int i=1;i<=n;i++){ ll now=Find(a[i].val); if(now==a[i].val){ Union(now,now+1); } else{ Union(now,now+1); ans=ans+a[i].w*(now-a[i].val); } } printf("%lld\n",ans); return 0; }
