Codeforces Round #645 (Div. 2) E. Are You Fired?(递推)

2020/7/10 8:45:34 人评论 次浏览 分类:学习教程

题目链接

传送门

题目大意

一个数组aa,有nn个元素,前n2\lceil \frac{n}{2} \rceil个元素是通过一一输入得到的,后n2\lfloor \frac{n}{2} \rfloor个元素全都为xx,是通过输入xx得到的。现在要求一个符合题意的kk:所有长度为kk的区间,区间和都要大于00

题目分析

首先要得到一个结论:k>n2k > \lfloor \frac{n}{2} \rfloor,简易证明:
假设kk存在且kn2k \le \lfloor \frac{n}{2} \rfloorbi=ai+ai+1+...+ai+k1b_i = a_i + a_{i+1} + ... +a_{i+k-1},则有:bi>0b_i > 0bi+k>0b_{i+k} > 0 (in2)(i \le \lfloor \frac{n}{2} \rfloor)。因为bib_ibi+kb_{i+k}都大于00,所以这两个可以拼凑成一个长度为2k2kci=bi+bi+k=ai+ai+1+...+ai+2k1>0c_i=b_i+b_{i+k}=a_i+a_{i+1}+...+a_{i+2k-1}>0。通过反复执行这个长度翻倍操作,最终可以使k>n2k > \lfloor \frac{n}{2} \rfloor

接着考虑枚举kk

  • k=n0k=n-0,有区间[1,n][1,n]
  • k=n1k=n-1,有区间[1,n1][1,n-1][2,n][2,n]
  • k=n2k=n-2,有区间[1,n2][1,n-2][2,n1][2,n-1][3,n][3,n]
  • k=n3k=n-3,有区间[1,n3][1,n-3][2,n2][2,n-2][3,n1][3,n-1][4,n][4,n]
  • k=n2+1k=\lfloor \frac{n}{2} \rfloor + 1,有区间[1,k][1,k][2,k+1][2,k+1]......[nk+1,n][n-k+1,n]

通过观察发现:当kk减少1时,区间长度减少11之前所有区间的区间和减少xx(这点很重要,自行理解一下为什么),新增了区间[nk+1,n][n-k+1,n]。所以,我们可以从大到小枚举kk,利用上述递推的关系,O(1)O(1)检查所有区间是否大于00(只需要维护最小的区间和与新增区间的和,检查是否大于0就可以了)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e5+5;

int a[maxn];
LL sum[maxn];

int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= (n+1)/2; i++) scanf("%d", &a[i]);

	int x;
	scanf("%d", &x);
	for(int i = (n+1)/2+1; i <= n; i++) a[i] = x;

	for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + a[i];

	LL minn = 1e18;
	for(int k = n; k >= n/2+1; k--) {
		LL t = sum[n] - sum[n-k];
		minn = min(minn, t);
		if(minn > 0) {
			printf("%d\n", k);
			return 0;
		}
		minn = minn - x;
	}
	printf("-1\n");

	return 0;
}

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->