专栏文章

题解：CF1358E Are You Fired?

yyingkeqian9217
CF1358E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipnpbjk
此快照首次捕获于
2025/12/03 14:59
3 个月前
此快照最后确认于
2025/12/03 14:59
3 个月前
查看原文
这里说一下不用分类讨论的简单做法。
注意到若 kk 合法，则 2k(2k<n)2k(2k<n) 也合法，故若有解则一定存在 k>⌈n2⌉k>\lceil \frac{n}{2}\rceil 合法。
记 m=⌈n2⌉m=\lceil \frac{n}{2}\rceil，后缀和数组 sufi=∑j=imajsuf_i=\sum_{j=i}^m a_j，即要求 min⁡i=1n−k+1sufi+(i+k−m−1)x>0\min_{i=1}^{n-k+1}suf_i+(i+k-m-1)x>0，参变分离即为 sufi+ixsuf_i+ix 的前缀最小值。
CPP
#include<bits/stdc++.h>
#define maxn 510005
#define int long long
using namespace std;
int n,m,x,a[maxn];
signed main(){
	scanf("%lld",&n),m=(n+1>>1);
	for(int i=1;i<=m;i++) scanf("%lld",&a[i]);
	scanf("%lld",&x);
	for(int i=m;i>=1;i--) a[i]+=a[i+1];
	int minn=1e18;
	for(int i=1;i<=m;i++){
		minn=min(minn,a[i]+x*i);
		if(minn+(n-m-i)*x>0) return printf("%lld\n",n-i+1),void();
	}
	puts("-1");
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...