-
天才ACM
原題鏈接
給定一個整數(shù)M夜畴，對于任意一個整數(shù)集合S辆布，定義“校驗值”如下：
從集合S中取出M對數(shù)（即2*M個數(shù)翠肘，不能重復(fù)使用集合中的數(shù)脊串，如果S中的整數(shù)不夠M對，則取到不能取為止）涎永，使得“每對數(shù)的差的平方”之和的最大涯保，這個最大值就成為集合S的“校驗值”
現(xiàn)在給定一個長度為N的數(shù)列A以及一個整數(shù)T。我們要把A分成若干段钞诡，使得每一段“校驗值”都不超過T郑现。求最少需要分成幾段？
即當(dāng)確定一個左端點L之后荧降，右端點R在A[L]~A[R]的校驗值不超過T的前提下接箫，最大能取到多少
倍增主要用于解決二分的缺點：如果每次詢問給定的整數(shù)T都非常小，造成答案k也非常小朵诫，那么該算法可能還不如從前向枚舉更優(yōu)
因此對于這道題：
1.初始化p=1,R=L=0辛友。
2.求出[L,R+p]這一段區(qū)間的“校驗值”，若“校驗值<=T”,則R+=p,p*=2剪返；否則p/=2
3.重復(fù)上一步废累，直到p的值變?yōu)?，此時R即為所求
int start=0,end=0;
while(end<n)
{
int len=1;
while(len)
{
if(end+len<=n&&check(start,end+len))//(范圍成立)&&(cheeck)
{
end+=len;//更新起點
len<<=1;//更新擴(kuò)大步伐
}
else
len>>=1;//縮小步伐
}
start=end;//前一部分已經(jīng)完成随夸，下一段起點從終點開始
}
時間復(fù)雜度：
以上過程最多循環(huán)O(logN)次九默，每次循環(huán)對長度為O(R-L)的一段進(jìn)行排序，完成整個題目的求解累計擴(kuò)展長度為N宾毒，因次總體時間復(fù)雜度為O(NlogN*logN)
優(yōu)化：
在處理 [start,end)[start,end) 的時候驼修，已經(jīng)將 [start,end)[start,end) 排好序了殿遂，所以不需要在處理 [start,end+len)[start,end+len) 時再排序。
處理 [start,end+len)[start,end+len) 時乙各，只需要將 [end,end+len)[end,end+len) 排序墨礁，然后將 [start,end)[start,end) 與 [end,end+len)[end,end+len) 這兩段區(qū)間進(jìn)行歸并即可。
假設(shè)一共將數(shù)組劃分成了 kk 個區(qū)間（這里的區(qū)間指的是每次二分里面check的區(qū)間總和耳峦，并非題目中所指的區(qū)間）恩静，每個區(qū)間的長度分別為 len1,len2,?,lenklen1,len2,?,lenk。
那么按上述方法只需要將每個區(qū)間排序一遍蹲坷，所以時間復(fù)雜度為 O(len1loglen1+len2loglen2+..+lenkloglenk)≤O(nlogn)
加上每次歸并的時間復(fù)雜度為O(n)驶乾，總的時間復(fù)雜度為 O(n+nlogn)=O(nlogn)
收獲一個精煉板塊
for(int i=0;i<k&&i<m;i++,k--)
sum+=sq(t[i]-t[k-1]);
//從最前(0)與最后(k-1)分別開始取最多m對,雙指針取數(shù)
-
解法一： 倍增O(NlogN*logN)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=500005;
int num,n,m;
ll T;
ll a[N],t[N],temp[N];
ll sq(ll x)
{
return x*x;
}
bool check(ll l,ll r)
{
int k=0;
for(int i=l;i<r;i++)
t[k++]=a[i];
sort(t,t+k);
ll sum=0;
for(int i=0;i<k&&i<m;i++,k--)//最多取m對,雙指針取數(shù)
sum+=sq(t[i]-t[k-1]);
return sum<=T;
}
int main()
{
scanf("%d",&num);
while(num--)
{
scanf("%d%d%lld",&n,&m,&T);
for(int i=0;i<n;i++)
scanf("%lld",&a[i]);
int ans=0;
ll start=0,end=0;
while(end<n)
{
ll len=1;
while(len)
{
if(end+len<=n&&check(start,end+len))//end從0開始可以取等號
{
end+=len;
len<<=1;
}
else
len>>=1;
}
start=end;
ans++;
}
printf("%d\n",ans);
}
return 0;
}
-
解法二：倍增+歸并(NlogN)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=500005;
ll a[N],t[N],temp[N];
ll num,n,m,T,ans;
ll sq(ll a)
{
return a*a;
}
bool check(ll l,ll mid,ll r)
{
for(int i=mid;i<r;i++)//復(fù)制數(shù)組，check嘗試可不可以循签，可能不可以的話级乐，就要重來，所以必須備份
t[i]=a[i];
sort(t+mid,t+r);
ll i=l,j=mid,k=0;
while(i<mid&&j<r)
{
if(t[i]<t[j])
temp[k++]=t[i++];
else
temp[k++]=t[j++];
}
while(i<mid)temp[k++]=t[i++];
while(j<r)temp[k++]=t[j++];
//計算校驗值
ll sum=0;
for(int i=0;i<m&&i<k;i++,k--)
sum+=sq(temp[i]-temp[k-1]);
return sum<=T;
}
int main()
{
scanf("%lld",&num);
while(num--)
{
scanf("%lld%lld%lld",&n,&m,&T);
for(int i=0;i<n;i++)
scanf("%lld",&a[i]);
ans=0;
ll len,start=0,end=0;
while(end<n)
{
len=1;
while(len)
{
if(end+len<=n&&check(start,end,end+len))// 如果 w 的 [start, end + len) 區(qū)間合法
{
end+=len,len<<=1;
if(end>=n)
break;
for(ll i=start;i<end;i++)//temp里存的是從0開始的歸并序列县匠，所以要減去start
t[i]=temp[i-start];
}
else
len>>=1;
}
start=end;
ans++;
}
printf("%lld\n",ans);
}
return 0;
}
