《算法竞赛进阶指南》天才ACM
给定⼀个整数 MM，对于任意⼀个整数集合 SS，定义“校验值”如下: 从集合 SS 中取出 MM 对数(即 2∗M2∗M 个数，不能重复使⽤集合中的数，如果 SS 中的整数不够 MM 对，则取到不能取为⽌)，使得“每对数的差的平⽅”之和最⼤，这个最⼤值就称为集合 SS 的“校验值”。
现在给定⼀个长度为 NN 的数列 AA 以及⼀个整数 TT。 我们要把 AA 分成若⼲段，使得每⼀段的“校验值”都不超过 TT。
求最少需要分成⼏段。
输⼊格式
对于每组测试数据，第⼀⾏包含三个整数 N,M,TN,M,T 。
第⼆⾏包含 NN 个整数，表⽰数列A1,A2…ANA1,A2…AN。
输出格式
对于每组测试数据，输出其答案，每个答案占⼀⾏。
数据范围
1≤K≤121≤K≤12,
1≤N,M≤5000001≤N,M≤500000,
0≤T≤10180≤T≤1018,
0≤Ai≤2200≤Ai≤220
输⼊样例：
2
5 1 49
8 2 1 7 9
5 1 64
8 2 1 7 9
输出样例：
2
1
仙人指路010#include<iostream>
#include<algorithm>
using namespace std;
#define sqr(a) (a)*(a)
#define ll long long
HOUSE OF SAND AND FOGconst int maxn=5e5+10;
ll a[maxn],b[maxn],p[maxn],k;
int n,m,ans=0,l=0,r=0;
void init(){
l=r=0;
ans=0;
cin>>n>>m>>k;//n为本组数据长度 , m为分段的最长对数 , k为最⼤差的平⽅和
破伤风抗毒素for(int i=1;i<=n;i++)
cin>>p[i];
}
void merge(int l,int mid,int r)8663部队张扣扣
{
int i=l,j=mid,k=l;
while(i<mid&&j<=r)
{
if(a[i]<a[j])
b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<mid)
while(i<mid)
b[k++]=a[i++];
while(j<=r)
b[k++]=a[j++];
}
bool check(int l,int mid,int r)
{//判断原来l~mid-1的数据合成mid~r的数据后的差的平⽅和是否符合题意
for(int i=mid;i<=r;i++)
a[i]=p[i];
sort(a+mid,a+r+1);
merge(l,mid,r);//对两段数据进⾏合并，此时合并的数据是存在临时数组b中的
ll sum=0;
for(int i=1;i<=(r-l+1)>>1&&i<=m;i++)//合成的这段数据最多可以构成(r-l+1)对数据且还要注意不能⼤于m对 sum+=sqr(b[r-i+1]-b[l-1+i]);
if(sum<=k)
{
for(int i=l;i<=r;i++)
a[i]=b[i];
return true;
}
return false;
}
void work(){
l=r=1;
a[l]=p[l];
int temp=1;//倍增的长度
while(r<=n)
{
if(!temp)
//重新设置倍增距离，新的⼀段开始，段的数量增加1
temp=1;多普达535
l=++r;
a[l]=p[l];
ans++;
}
else if(r+temp<=n&&check(l,r+1,r+temp))
{//当增加的这段距离不超过最⼤距离，且差的平⽅和也不超过k时长度增加，倍增距离也增加
r+=temp;
if(r==n)break;
temp<<=1;
}
else//增加的距离不符合条件时，减⼩增加的距离
temp>>=1;
}
if(r==n)开放式数控系统
ans++;//当最后也恰好构成⼀段时段数加⼀
}
int main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
init();
work();
cout<<ans<<endl;
}
return0;
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议