通过写这个题,我居然明白了为什么STL都用的是左闭右开区间…这玩意实在是比闭区间好操作的多了.
首先,计算一个区间的”校验值”就直接贪心排序,然后每次选最大的和最小的配对就好了.
那么这个题肯定是可以用二分长度+贪心来写,时间复杂度$O(nlog^2n)$
考虑优化:
- 倍增优化:对于每次拓展的长度都很小的情况,二分本身会跑满log.使用倍增:(设当前考虑的区间起始点为start)
1.先钦定当前倍增长度pw=1.钦定区间结尾为end,表示当前正在考虑[start,end)是否合法.
2.将[start,end+pw)排序,求其校验值.若不超过k,令end+=k,pw<<=1(此时如果end>n,表示已处理完毕,直接break);否则,pw>>=1;
3.重复2,直至其主动跳出或pw==0
4.令start=end,并重复这四步
这个优化大大减小了算法的运行常数,但没有真正改变时间复杂度,应对5e5还是比较困难. - 排序优化:在”倍增优化”中,可以发现[start,end)实际上已经有序,再重新排序属于浪费时间.我们只需要对[end,end+pw)排序,然后与[start,end)线性合并即可.这样优化后,时间复杂度将为$O(nlogn)$(但我不会证明这个,wtcl)
这个题的代码也不太好写,我贴一下,供参考:
//Wan Hong 3.0
//notebook
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <map>
typedef unsigned un;
typedef long long ll;
typedef std::pair<ll,ll> pll;
const ll INF=1ll<<58;
ll read()
{
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
bool umin(ll &a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
bool umax(ll &a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
ll abs(ll x)
{
return x>0?x:-x;
}
/**********/
#define MAXN 500011
ll a[MAXN],t[MAXN],tmp[MAXN];
ll n,m,k;
void merge(ll l,ll mid,ll r)//merge [l,mid) and [mid,r)
{
ll itl=l,itr=mid,k=l;
while(itl<mid&&itr<r)
{
if(t[itl]<=t[itr])tmp[k++]=t[itl++];
else tmp[k++]=t[itr++];
}
while(itl<mid)tmp[k++]=t[itl++];
while(itr<r)tmp[k++]=t[itr++];
}
bool check(ll l,ll mid,ll r)//whether the value of [l,r) is less than k.[l,mid) has been sorted.
{
if(r>n)r=n+1;
for(ll i=mid;i<r;++i)t[i]=a[i];
std::sort(t+mid,t+r);
merge(l,mid,r);
ll sum=0,w=min(m,(r-l)>>1);
for(ll i=1;i<=w;++i)
sum+=(tmp[r-i]-tmp[l+i-1])*(tmp[r-i]-tmp[l+i-1]);
return sum<=k;
}
int main()
{
ll task=read();
while(task--)
{
n=read(),m=read(),k=read();
for(ll i=1;i<=n;++i)a[i]=read();
ll ans=0,start=1,end=1;//[start,end) has been sorted.
while(start<=n)
{
++ans;
ll pw=1;
while(pw)
{
if(check(start,end,end+pw))//whether the value of [start,end+pw) is less than k
{
end+=pw;
if(end>n)break;
for(ll i=start;i<end;++i)t[i]=tmp[i];
pw<<=1;
}
else pw>>=1;
}
start=end;
}
printf("%lld\n",ans);
}
return 0;
}
%%%
大佬膜酸菜鱼竟是因为…