题目
题解
参考题解：
https://www.acwing.com/solution/content/15458/
很好。
首先考虑我们用贪心证明两个东西：
- 如果第(i)个可以归到前面的部分就归到前面的部分，不要放到后面的部分，反正放到后面也只会让校验值增大，还不如不放。
- 对于一个数列而言，如何求校验值？答案是最大的减最小的的平方加上次大的...。
至于证明，首先，如果对于((x-y)^2(x>y))，而数列中有 没有用的比(x)更大或比(y)更小的数字的话，那么我们肯定要用啊。
第二，对于(a<b<c<d)而言，最大的方案肯定是：((a-d)^2+(b-c)^2)，要证明的话全部化成平方和就变成了问两两数字相乘最小的问题了：(a^2+b^2+c^2+d^2-2ad-bc)，这个大家肯定都会证明的吧，不会证明看这里：
通过这两个结论就可以证明了。
方法1
因为长度越长校验值越大，根据这个可以二分，也就是二分+check，但是如果每个块都很小的话时间复杂度就很容易被卡成：(O(Kn^2log^2n))，。
方法2
这个时候就要用到倍增了，倍增算法完美解决了二分处理小数据时无力的问题，倍增的流程是：
- 确定一个(x=1,R=1)，然后如果([1,R+x])可以的话，那么(R+=x,x<<=1)，并重复1操作，但是如果不可以的话，(x>>=1)并跳到2操作。
- 如果[1,R+x]可以的话，(R+=x)，不管可不可以，(x>>=1)并重复2操作直到(x=0)。
当然还有一种较慢的倍增：是如果不可以(x>>=1)，可以(x<<=1)，但是会慢（因为其实也是跟上面一样的流程，但是在2步骤中一旦可以会(x<<=1)又要花一次(x>>=1)来重回正轨）。
（其实我一开始的写法是是1操作没有(R+=x)，跳到2操作时再(R=x)，但是没必要，还会慢）
当然，上面的三种做法，单次的时间复杂度都是(O(log{t}))（(t)为最终的(R)），因此倍增是一个时间复杂度很优秀的算法，而且在处理数据块很小时更是展现出比二分大得多的优越性。（至于为什么，你可以把第一个步骤看成找最大(?)使得(2^{?}-1≤t)，至于第二个步骤，则是又把(?)遍历一遍，所以是(O(log{t}))）
采用快速排序的时间复杂度是(O(nlog^2n))。
证明我先写的下面的证明，哈哈：
设第(i)个块长度为(l_i)，且在倍增第一个步骤中(x)最大去到了(xx)。
注：计算校验值的时间复杂度是块长，而排序的复杂度大于等于块长，因此默认忽略校验值的时间复杂度计算。
第一个步骤是一个(log)，我们不管他，我们要证的是第二个步骤，第一个步骤完毕后，确定的(R)大于等于(frac{l_i}{2})，因为要check (logl_i)次，所以时间复杂度为：(O(Rlogl_ilogR)=R(l_ilog^2l_i))。
所有块合并起来的时间复杂度就是：(O(nlog^2n))。
常数小可以AC此题。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 510000
using namespace std;
int a[N],b[N],n,m;
long long T;
inline int mymin(int x,int y){return x<y?x:y;}
bool check(int x,int now)
{
int l=now+1,r=x+now;
int t=0;
for(int i=l;i<=r;i++)b[++t]=a[i];
sort(b+1,b+t+1);
int f=t/2;
long long ans=0;
for(int i=mymin(f,m);i>=1;i--)ans+=(long long)(b[t-i+1]-b[i])*(b[t-i+1]-b[i]);
return ans<=T;
}
int main()
{
int K;scanf("%d",&K);
while(K--)
{
scanf("%d%d%lld",&n,&m,&T);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int now=0,ans=0;
while(now<n)
{
int cnt=1,R=1;
while(check(mymin(R+cnt,n-now),now)==1)
{
R+=cnt;
if(R>n-now){R=n-now;break;}
cnt*=2;
}
if(cnt!=n-now)
{
cnt/=2;
while(cnt)
{
if(check(mymin(R+cnt,n-now),now)==1)
{
R+=cnt;
if(R>n-now){R=n-now;break;}
}
cnt>>=1;
}
}
now+=R;
ans++;
}
printf("%d
",ans);
}
return 0;
}
方法3
我们上面采用的是快速排序，但是如果用类似归并排序的方法呢？
即我现在已经知道了(X)，然后要对(X+Y)进行排序，那么就对(Y)进行排序，然后合并。
这个优化在较快的倍增中的第一个步骤中是毫无优化的，因为：(frac{n}{2}*log {frac{n}{2}}*2+n=nlog{n})。
但是再第二个步骤中，就不会因为长度较小的(Y)而重复排序了，优化程度很大。
（下面证明用的是目前讲的最快的倍增打法）
那么我们现在就来证明一波时间复杂度：
设第(i)个块长度为(l_i)，且在倍增第一个步骤中(x)最大去到了(xx)。
注：计算校验值的时间复杂度是块长，而排序的复杂度大于等于块长，因此默认忽略校验值的时间复杂度计算。
对于第一个步骤而言：(O(1*log(1)+3*log(2)+7*log(4)+...+(2*xx-1)*log(xx)+(4*xx-1)*log(xx*2))=O(xxlog{xx}))（根据(a_1log{a_1}+a_2log{a_2}+...+a_ilog{a_i}≤sumlog{sum})得出，(sum)为总和）
对于第二个步骤而言：
合并的话，即使假设单次合并的的时间是最终块长的两倍，那么时间复杂度也是：(O(log_{l_i}l_i))，所以就是分析快速排序的时间复杂度：(O(1*log(1)+2*log(2)+4*log(4)+...+frac{xx}{2}*log(frac{xx}{2})=O(xxlog{xx}))，因此对于一个块而言，时间复杂度即为：(O(l_ilog{l_i}))，所有块时间复杂度一合并，就是(O(nlogn))了。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 500005;
int n, m;
int ans;
ll T;
ll w[N], t[N];
ll tmp[N];
ll sq(ll x)
{
return x * x;
}
bool check(int l, int mid, int r) // 判断区间 [l, r) 是否合法，并将 t 中的 [l, mid) 区间和 [mid, r) 区间合并到 tmp 中
{
for (int i = mid; i < r; i ++ ) // 将 w 数组的 [l, r) 区间复制到 t 的 [l, r) 区间中
t[i] = w[i];
sort(t + mid, t + r); // 将 t 的 [mid, r) 排序
int i = l, j = mid, k = 0; // 双指针进行区间合并
while (i != mid && j != r) // 当 i 不到 mid 且 j 不到 r 时，执行循环
if (t[i] < t[j]) // 如果 t[i] 比 t[j] 小，那么将 t[i] 放入 tmp 中
tmp[k ++ ] = t[i ++ ];
else // 否则将 t[j] 放入 tmp 中
tmp[k ++ ] = t[j ++ ];
while (i != mid) tmp[k ++ ] = t[i ++ ]; // 处理剩下的元素
while (j != r) tmp[k ++ ] = t[j ++ ];
ll sum = 0; // 计算校验值
for (i = 0; i < m && i < k; i ++ , k -- )
sum += sq(tmp[i] - tmp[k - 1]);
return sum <= T; // 返回当前区间 [l, r) 是否合法
}
int main()
{
int K;
scanf("%d", &K);
while (K -- )
{
scanf("%d %d %lld
", &n, &m, &T);
for (int i = 0; i < n; i ++ )
scanf("%lld", &w[i]);
ans = 0;
int len;
int start = 0, end = 0;
while (end < n)
{
len = 1;
while (len)
{
if (end + len <= n && check(start, end, end + len)) // 如果 w 的 [start, end + len) 区间合法
{
end += len, len <<= 1;
if (end >= n) break ; // 一个小剪枝，如果 end >= n，那么直接跳出
for (int i = start; i < end; i ++ ) // 在 check 时，已经将 t 数组的 [start, end + len) 这段区间归并在 tmp 中了。现在只需要将 tmp 中的有序数组复制到 t 中即可
t[i] = tmp[i - start]; // 复制的时候注意下标变换，tmp 是从 0 开始存的，t 是从 start 开始存的
}
else len >>= 1;
}
start = end;
ans ++ ;
}
printf("%d
", ans);
}
return 0;
}
作者：垫底抽风
链接：https://www.acwing.com/solution/content/15458/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。