题目描述
题目描述
给定一个整数 MM,对于任意一个整数集合 SS,定义“校验值”如下:
从集合 SS 中取出 MM 对数(即 2∗M2∗M 个数,不能重复使用集合中的数,如果 SS 中的整数不够 MM 对,则取到不能取为止),使得“每对数的差的平方”之和最大,这个最大值就称为集合 SS 的“校验值”。
现在给定一个长度为 NN 的数列 AA 以及一个整数 TT。
我们要把 AA 分成若干段,使得每一段的“校验值”都不超过 TT。
求最少需要分成几段。
输入格式
第一行输入整数 KK,代表有 KK 组测试数据。
对于每组测试数据,第一行包含三个整数 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≤220
样例
样例
输入样例:
2
5 1 49
8 2 1 7 9
5 1 64
8 2 1 7 9
输出样例:
2
1
这一题忒狠了,参照秦淮岸大佬代码,此题用到倍增思想,不断扩展区间,
分成段数要最少,则每一段要尽可能的大,
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define sqr(a) (a)*(a)
const int N=5e5+10;
int n,m,p[N],a[N],ans,l,r;//ans记录分成段数
ll b[N],k;
void merge(int l,int mid,int r)
{
int i=l,j=mid;
for(int k=l;k<=r;k++)
if(j>r||i<mid&&a[i]<=a[j]) b[k]=a[i++];
else b[k]=a[j++];
}
bool check(int l,int mid,int r)
{
fir(i,mid,r)
a[i]=p[i];
sort(a+mid,a+r+1);//对新增的另一半排序
merge(l,mid,r);//最后一次归并,对整段排序
ll sum=0;
for (int i=1; i<=(r-l+1)/2 && i<=m; i++)//
sum+=sqr(b[r-i+1]-b[l+i-1]);
if (sum<=k)
{
for (int i=l; i<=r; i++)//记录已经排好的顺序
a[i]=b[i];
return true;
}
return false;
}
void work()
{
int len=1;
l=r=1;
a[l]=p[l];//存储第一个元素,才能不断对另一半排序
while (r<n)
if (!len)//已经找到符合要求的一段
{
len=1;
ans++;
l=++r;
a[l]=p[l];
}
else if (r+len<=n && check(l,r+1,r+len))
{
r+=len;
len<<=1;//长度翻倍
}
else
len>>=1;//
if (r==n)
ans++;
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while (t--)
{
ans=0;//重置为0
cin>>n>>m>>k;
fir(i,1,n)
cin>>p[i];
work();
cout<<ans<<endl;
}
return 0;
}