求助,75分挂小数据,码风良好有注释
  • 板块P6155 修改
  • 楼主Misakura_Rin
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/7/25 11:34
  • 上次更新2024/7/25 13:22:00
查看原帖
求助,75分挂小数据,码风良好有注释
462050
Misakura_Rin楼主2024/7/25 11:34
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define llu unsigned long long
#define MAXN (int)1e6+5
using namespace std;
int n;
llu a[MAXN],b[MAXN];
llu des[MAXN];
llu ra[MAXN];
llu plu[MAXN];
priority_queue<llu,vector<llu>,less<llu> > maxQue;
llu ans=0;
int main(){
	//读入
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%llu",a+i);
	for(int i=1;i<=n;i++)scanf("%llu",b+i);
	//排序,都升序排
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	//计算每个元素要修改到的位置des[i]
	for(int i=1;i<=n;i++){
		des[i]=max(des[i-1]+1,a[i]);
	}
	//大体思路:弄一个大根堆,然后由1~N遍历刚刚求的des[i]然后取出一个小于des[i]的最大a[i]值计入ra[i]
	int k=1;
	for(int i=1;i<=n;i++){
		while(k<=n&&a[k]<=des[i]){
			maxQue.push(a[k]);
			k++;
		}
		ra[i]=maxQue.top();
		maxQue.pop();
	}
	//然后计算每个元素要修改的次数plu[i]
	for(int i=1;i<=n;i++)plu[i]=des[i]-ra[i];
	//大plu乘小b来使最终结果最小
	for(int i=1;i<=n;i++)ans+=plu[i]*b[n-i+1];
	printf("%llu",ans);
	return 0;
}
2024/7/25 11:34
加载中...