CF978E Bus Video System【数学/前缀和/思维】

【链接】:

CF

【分析】:

设上车前人数 x ,中途最大人数为 x+max ,最小人数为 x+min (max≥0,min≤0)

可得不等式组 x+max≤w, x+min≥0

整数解个数为 max(0,w-max+min+1)

求出 max,min 即可,有求和~记得long long

【代码】:

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a); i<(b); i++)
const int N = 2*1e5+5;
int main()
{
int n,m,x;
long long sum=0,Max=0,Min=0;
scanf("%d%d",&n,&m);
rep(i,0,n)
{
scanf("%d",&x);
sum+=x;
Min=min(Min,sum);
Max=max(Max,sum);
}
cout<<max(0LL,m-Max+Min+1);
/*
Max=m-Max;
Min=-Min;
int ans=Max-Min+1;
if(ans<=0) puts("0");
else printf("%d\n",ans);
*/
return 0;
} /*
3 5
2 1 -3
3 0
3
//////////
2 4
-1 1
0 -1
4
/////////
4 10
2 4 1 2
9 0
2
*/
上一篇:P2240 【深基12.例1】部分背包问题


下一篇:半导体和集成电路发展 | 计算机百年趣味史(上)第4篇