• 欢迎光临~

luogu P6155 修改题解

开发技术 开发技术 2022-10-06 次浏览

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;
}

程序员灯塔
转载请注明原文链接:luogu P6155 修改题解
喜欢 (0)