CF978E Bus Video System 题解

wuyixiang · 2023-08-15 14:38:40 · 题解

题目大意：一辆大巴车，到每个站点会下车 -a_i 或上车 a_i 人，但是任意一个时刻大巴车的总人数都应该在 0 至 w 人之间，问一开始大巴车上的人数有几种可能。

思路分析：一道简单的贪心题。

把 a 数组遍历完之后，我们可以得知车上在任意一个时刻最多会增加 maxx 人，减少 minn 人。所以一开始车上的人数，必须 +maxx \le w，-minn \ge 0。所以车上的人数只有可能是 minn 至 w - maxx 人，那么就会有 w - maxx - minn + 1 种方案。注意：如果 minn > w - maxx，就说明不存在可能性，应当输出 0。

AC code:

#include <iostream>
using namespace std;
long long n,w,a,maxx,minn,num ;//不开long long见祖宗
int main()
{
    cin >> n >> w;
    for(int i = 1;i <= n;i ++)
    {
        cin >> a;
        num += a;
        maxx = max(maxx,num),minn = min(minn,num);//更新最大与最小
    }
    cout << max(w - maxx + minn + 1,0LL);//注意这里的minn是负数，应改成+号
}