自动搬运

查看原文

来自洛谷，原作者为

	gyh20 orz Feecle6418

搬运于2025-08-24 22:17:59，当前版本为作者最后更新于2020-02-17 23:13:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

首先，如果没有 $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);
}