正经题解|好坏消息
2024-08-24 17:48:25
发布于:广东
9阅读
0回复
0点赞
ok呀这道题也是肥肠简单啊,但是我被他卡了足足20分钟原因是k=n时也可以而我没判断,太坑了
这道题就是维护前缀和还有前后缀最小值,然后遍历一遍判断一下就行了,详见代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+5;
int a[N],s1[N],s2[N];
int main() {
int n;
scanf("%d",&n);
s1[0]=s2[n+1]=2e9;
for (int i=1;i<=n;i++) {
scanf("%d",&a[i]);
a[i]+=a[i-1];
s1[i]=min(s1[i-1],a[i]);
}
for (int i=n;i>=1;i--) {
s2[i]=min(s2[i+1],a[i]);
}
int cnt=0;
for (int i=1;i<=n;i++) {
if (s2[i+1]-a[i]>=0&&s1[i]+(a[n]-a[i])>=0) {
cnt++;
}
}
printf("%d",cnt);
return 0;
}
这里空空如也
有帮助,赞一个