AcWing 109. 天才ACM（倍增+归并排序）

傷城~ 2021-12-09 17:01 198阅读 0赞

给定一个整数 M，对于任意一个整数集合 S，定义“校验值”如下:从集合 S中取出 M对数(即 2∗M个数，不能重复使用集合中的数，如果 S中的整数不够 M对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合 S的“校验值”。现在给定一个长度为 N的数列 A以及一个整数 T。我们要把 A分成若干段，使得每一段的“校验值”都不超过 T。求最少需要分成几段。

输入格式  
第一行输入整数 K，代表有 K组测试数据。对于每组测试数据，第一行包含三个整数 N,M,T。第二行包含 N个整数，表示数列A1,A2…AN。输出格式对于每组测试数据，输出其答案，每个答案占一行。数据范围1≤K≤12，1≤N,M≤500000,0≤T≤1018,0≤Ai≤220

输入样例：  
2  
5 1 49  
8 2 1 7 9  
5 1 64  
8 2 1 7 9

输出样例：  
2  
1

知识点：  
倍增，字面意思是“成倍增长”。如果我们在进行递推时，如果状态空间很大，通常的线性递推无法满足时间与空间复杂度的要求，那么我们可以通过成倍增长的方式，只递推状态空间中在2的整数次幂的位置上的值作为代表。  
倍增与二进制划分的两个思想相互结合，降低了求解很多问题的时间与空间复杂度。有种快速求a的b次幂是快速幂，快速幂就是倍增与二进制划分思想的一种体现。

问题一：校验值怎么求最大，排序后（最大的-最小的 的平方）+（次大的-次小的 平方 ）… 不证明了，很简答。

问题二：如何求段数最小，也就让每段尽可能的长，  
方法有三种：  
1.暴力，每次长度+1，每次都排序再比较校验值是都满足条件，O（n*n*logn）这复杂度谁顶得住啊…  
2.二分，每次取总集合长度一半来判断校验值，但是一旦某个集合较短，而总集合很长，二分的方法必然会产生慢收敛现象，很久才能搜到解。  
3.倍增，第一次往后增加1个长度，如果满足条件增加2个长度，继续满足增加4个长度… 直到不满足减少增加一般的长度，一直减少一般的长度…O（n*logn*logn）本题数据500000，TLE。所以我们需要优化，就是第三个问题。

问题三：我们分析一下时间多的原因，每次增加或减少长度O（logn倍增）每次排序都需要O（n*logn） 是排序比较费时间。那我们优化一下，首先增加或减少长度之前的那段序列已经是有序的，如果增加或减少了长度又排序，很费时，所以我们只需要排序新增的那一段就可以，然后用归并排序把两个序列合并O（n），时间复杂度优化到O（n*logn）=排序（n\*logn）+ 归并两个序列（n）+操作检验数（n）

如果有同学问，如果增加了长度排序后不满足条件怎么办，这个只需要多开一个辅助数组就行了。

代码：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    const int mmax=500010;
    ll n,m,k,w;
    ll a[mmax],b[mmax],c[mmax];
    void merge(ll l,ll mid,ll r)
    {
    	ll i=l,j=mid+1;
    	for(int k=l;k<=r;k++)
    	{
    		if(j>r||(i<=mid&&b[i]<=b[j]))
    			c[k]=b[i++];
    		else 
    			c[k]=b[j++];
    	}
    }
    ll work(ll l,ll r)
    {
    	if(r>n) r=n;
    	ll t=min(m,(r-l+1)>>1);
    	for(int i=w+1;i<=r;i++)
    		b[i]=a[i];
    	sort(b+w+1,b+r+1);
    	merge(l,w,r);
    	ll num0=0;
    	for(int i=0;i<t;i++)
    	{
    		num0+=(c[r-i]-c[l+i])*(c[r-i]-c[l+i]);
    	}
    	return num0;
    }
    void solve()
    {
    	cin>>n>>m>>k;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>a[i];
    	}
    	ll ans=0,l=1,r=1,p;
    	w=1;
    	b[1]=a[1];
    	while(l<=n)
    	{
    		p=1;
    		while(p)
    		{
    			ll num=work(l,r+p);
    			if(num<=k)
    			{
    				w=r=min(n,r+p);
    				for(int i=l;i<=r;i++)
    					b[i]=c[i];
    				if(r==n)	break;
    				p<<=1;
    			}
    			else
    			{
    				p>>=1;
    			}	
    		}
    		ans++;
    		l=r+1;
    	}
    	cout<<ans<<endl;
    }
    int main()
    {
    	ios::sync_with_stdio(false);
    	ll T;
    	cin>>T;
    	while(T--)
    	{
    		memset(a,0,sizeof(a));
    		memset(b,0,sizeof(b));
    		memset(c,0,sizeof(c));
    		solve();
    	}
    	return 0;
     }