《算法竞赛进阶指南》0x06倍增 Acwing GeniusACM
标签：端点 style long script cst == 指南 集合 iostream
题目链接：https://www.acwing.com/problem/content/description/111/
首先定义了集合S的校验值，取出m对数，使得每对平方之后求和最大，这个值成为集合S的校验值。现在给定一个数列，求满足每段的校验值小于T的前提下最小能把数列分成连续的几段？
利用倍增的思想对右端点进行倍增，并且结合归并排序去除冗余的排序。具体解释在代码中阐明。二进制就是这么神奇而高效。
代码如下：
#include
#include
#include
using namespace std;
#define maxn 500010
typedef long long ll;
int n,m,ed;
ll k;//注意k是1e18范围的
ll a[maxn],b[maxn],c[maxn];//a:无序，原数组，b:分两段有序，c:归并之后的合并数组
void gb(int l,int mid,int r){//[l,mid]与[mid+1,r] 归并，
int i=l,j=mid+1;//双指针扫描
for(int k=l;k){
if(j>r || (i];
else c[k]=b[j++];
}
}
ll calc(int l,int r){//计算校验值
if(r>n)r=n;
int t=min((r-l+1)/2,m);//将[l,r]区间分成的最大的对数
ll ans=0;
for(int i=ed+1;i//将a[i]中上次mid+1的位置到r的序列放入b中并排序
sort(b+ed+1,b+r+1);//[ed+1,r]部分排序
gb(l,ed,r);
for(int i=0;i){
ans+=(c[r-i]-c[l+i])*(c[r-i]-c[l+i]);
}
return ans;
}
void Genius_ACM(){
int ans=0;//分的段数
int l=1,r=1;
b[1]=a[1];
ed=1;//ed表示的是上次倍增的结束位置
while(ln){
int p=1;//每一段都是从2^0开始倍增的
while(p){
ll num=calc(l,r+p);
if(numk){
ed=r=min(r+p,n);
for(int i=l;i//将归并的有序序列放入b中
if(r==n)break;
p1;
}else p>>=1;//倍增失败，缩小倍增跨度
}
ans++;
l=r+1;
}
coutendl;
}
int main(){
int t;
cin>>t;
while(t--){
cin>>n>>m>>k;
for(int i=1;i"%lld",&a[i]);
Genius_ACM();
}
return 0;
}
《算法竞赛进阶指南》0x06倍增 Acwing GeniusACM
标签：端点 style long script cst == 指南 集合 iostream
原文地址：https://www.cnblogs.com/randy-lo/p/13137638.html
评论