Codeforces Round #645-E
题意分析
给定一个长度为(n)的数组(arr),第((lceil{frac{n}{2}} ceil+1)-n)项相同均为x,即(arr[ ]={ arr_1,arr_2……arr_{lceil{frac{n}{2}} ceil},x,x,……})。
问是否存在k使得
若存在输出任意一个k,否则输出-1。
解题思路
暴力做法
从1到n枚举k,然后检测k是否可行。
如何检测给定的k是否可行?计算出所有(s_i=sum_{i=p}^{p+k-1}arr_i),若存在(s_ileq 0)则不可行,否则可行。一次检测时间复杂度为(O((n-k+1) imes k))。观察(s_i)之间的关系发现:
于是可以采用递推的方式计算(s_i),因此一次检测的时间复杂度为(O(n-k+1))。
所以检测所有k的时间复杂度为
而n的最大取值为(5 imes10^5),所以暴力法不可行。
改进做法
题目中有一个重要的性质没有用到:第((lceil{frac{n}{2}} ceil+1)—n)项相同均为x。(启发式经验,尝试用此性质找到不同k的检测之间的关系)
观察递推公式(1),假设(kgeqlceil{n/2} ceil),于是公式(1)改写为
进而推导出:
当长度为k增1,公式(3)依然成立。于是当(kgeqlceil{n/2} ceil)为真时,(s_{i+1}-s_{i}=x-arr_i)。
根据公式(3)为相邻两项差的形式,所以尝试用前缀和数组的形式来进一步推导。
构造长度为k时计算(s_i)的前缀和数组:
长度为k+1时计算(s_i)的前缀和数组:
通过观察发现(P^{K+1})和(P^{K})十分相似,所以考虑他们答案之间的递推关系。假设(P^{K+1})的
则为(P^K)的
即(P^K)的前n-k个前缀和中的最小值可以由(P^{k+1})的最大前缀和推导出。而(P^K)的最后一个前缀和(s_{n-k+1})为(P^K)的全部元素的和(sum P^K),且
则(P^K)的所有前缀和中最小值为
由此我们找到了(kgeqlceil{n/2} ceil)时(h_k)的递推关系式,而(h_n)的值即为(sum arr_i)。所以从(h_n)出发使用公式(4)即可在(O(N))的时间内检测所有(kgeqlceil{n/2} ceil)的情况。
还剩下一个问题,(k<lceil{n/2} ceil)的情况怎么办?如果我们在检测所有(kgeqlceil{n/2} ceil)的情况时发现存在解,那(k<lceil{n/2} ceil)的情况就无需检测了,但如果没有发现解则需要进行检测。真的需要检测吗?
假设存在一个(k<lceil{n/2} ceil)的解,则(2 imes kgelceil{n/2} ceil)必然也是解,想想就可以知到,每一个长度为的子段的和大于0,那么连续两个长度为k的子段和之和必然也大于0。所以无需检测这类情况。
算法总结
利用公式(4)检测(kgeqlceil{n/2} ceil)的情况,在O(N)的时间复杂度内解决此题。
//一份几乎无法让人看懂的题解,写完后我也不想看。。。。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=5e5+10;
int arr[MAXN];
int main() {
ll n,x;
scanf("%lld",&n);
ll mid;
mid=(n+1)/2;
ll sum = 0,premin;
for(int i=1;i<=mid;i++){
scanf("%d",arr+i);
sum=sum+arr[i];
}
scanf("%lld",&x);
for(int i=mid+1;i<=n;i++){
arr[i]=x;
}
sum+=(ll)(n-mid)*(ll)x;
premin=sum;
int ans=-1;
for(int i=n;i>=mid;i--){
if(premin>0){
ans=i;
break;
}
else{
sum=sum-arr[i]+x-arr[n-i+1];
premin=premin-arr[i];
premin=min(premin,sum);
}
}
printf("%d",ans);
return 0;
}