天才ACM

给定一个整数m，定义一个集合的权值为从这个集合中任意选出m对数（不够没关系，选到尽可能选，凑不成对的舍去），每对数两个数的差的平方的和的最大值。

现在给出一个数列$\{a_i\}$，询问最少的区间划分数，让它每个区间的权值不超过p（p已给定），$1≤n,m≤500000,0≤p≤10^{18}$

解

首先注意到从集合中选出m对数，让每对数的差的平方的和最大值为一个贪心模型，我们只需要将集合中的元素按从小到大排序，然后把最大数和最小数配对，再将次大数和次小数配对，依次类推即可。

而只要每个区间都尽可能大，那么就是最优方案，于是原问题也就转化为确定了一个左端点，右端点在哪个位置，使权值最大化，不超过p。

法一：二分

考虑二进制优化，于是想到二分，注意到这类似二分模型，比最优方案大就无解，比最优方案小就有解，于是可以考虑二分右端点的位置mid，设二分区间为$[l,r]$，而判断和p的大小关系，就暴力求出二分出来的区间的权值小于p，那么$l=mid+1$，否则$r=mid-1$，对于权值如何求，就暴力排序，暴力配对，于是可以做到时间复杂度$O({\large nlog_2^{n^2}})$。

事实证明这个算法萎了，但还是给出代码。

参考代码

#include <iostream>

#include <cstdio>

#include <algorithm>

#define il inline

#define ri register

#define ll long long

#define Size 500100

using namespace std;

int m,a[Size],b[Size];

template<class free>

il void read(free&);

il ll powsum(int,int);

il int dfs(int,int,int);

int main(){

	int lsy;read(lsy);

	while(lsy--){

		int n,l(1),tot(0);ll T;

		read(n),read(m),read(T);

		for(int i(1);i<=n;++i)read(a[i]);

		while(l<=n)l=dfs(l,n,T),++tot;

		printf("%d\n",tot);

	}

	return 0;

}

il ll powsum(int l,int r){

	int i,j,m(::m);ll ans(0);for(i=l;i<=r;++i)b[i]=a[i];sort(b+l,b+r+1);

	i=l,j=r;while(i<=j&&m)ans+=(b[i]-b[j])*(b[i]-b[j]),++i,--j,--m;

	return ans;

}

il int dfs(int l,int r,int T){

	int mid,s(l);

	while(l<=r){

		mid=l+r>>1;

		if(powsum(s,mid)>T)r=mid-1;

		else l=mid+1;

	}return l;

}

template<class free>

il void read(free &x){

	x^=x;ri char c;while(c=getchar(),c<'0'||c>'9');

	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();

}

法二：

实际上二进制优化家族中还有倍增，这一有力工具，但要注意思维的开放，如果找老套路从高位开始试填的话，你就会死的与二分一样惨。

不妨声明变量$l,r,nr,J$，分别表示确定的左端点位置，已经确定的右端点，尝试确定的右端点，一次要往前看的范围为$2^J。

因此每次操作可以这样，先令$nr=r+2^J$，然后查看区间$[l,nr]$的权值与p的关系，如果比p大，则只令$--J$，否则$r=nr,++J$。

至于权值怎么办？如果照着老套路，那么又是$?$了，根据维护的思想，凭借已有的东西求出未知的东西，我们发现我们已经有了一段序列是有序的，没必要再把整个区间重新排序去检查，我们只需要把因为试填而带出来的新区间进行排序，然后和原来的区间归并，这样就可以做到梦寐以求的$O(nlogn)$了。

参考代码：

#include <iostream>

#include <cstdio>

#include <algorithm>

#define il inline

#define ri register

#define ll long long

#define Size 500050

using namespace std;

int a[Size],b[Size],t[Size];

il ll powsum(int,int,int,int[]);

il void merge(int,int,int,int[]);

template<class free>il void read(free&);

int main(){

	int lsy;read(lsy);

	while(lsy--){int i,j,tot(0);ll T;

		int n,m,l(1),r(1),nr,mj(1);

		read(n),read(m),read(T);

		for(i=1;i<=n;++i)read(a[i]);b[1]=a[1];

		while(r<n){//attention

			nr=r+mj;if(nr>n)nr=n;

			for(i=r+1;i<=nr;++i)b[i]=a[i];

			sort(b+r+1,b+nr+1),merge(l,r,nr,b);

			if(powsum(l,nr,m,t)>T)mj>>=1;

			else{

				r=nr,mj<<=1;

				for(i=l;i<=r;++i)b[i]=t[i];

			}

			if(!mj)l=r+1,mj=1,++tot;

		}printf("%d\n",tot+1);

	}

	return 0;

}

il ll powsum(int l,int r,int m,int a[]){ll ans(0);

	while(l<=r&&m)ans+=(ll)(a[r]-a[l])*(a[r]-a[l]),++l,--r,--m;

	return ans;

}

il void merge(int l,int mid,int r,int a[]){

	int i(l),j(mid+1),k(l);

	while(i<=mid&&j<=r)

		if(a[i]<a[j])t[k++]=a[i++];

		else t[k++]=a[j++];

	while(i<=mid)t[k++]=a[i++];

	while(j<=r)t[k++]=a[j++];

}

template<class free>

il void read(free &x){

	x^=x;ri char c;while(c=getchar(),c<'0'||c>'9');

	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();

}

巴特西

天才ACM

解

最新文章

热门文章