MENU

Code Forces Round #668(Div.2)

September 7, 2020 • Read: 227 • 题解

Code Forces Round #668(Div.2)

B. Array Cancellation

题目链接:https://codeforces.com/contest/1405/problem/B

题目原文:

image-20200907205020594

image-20200907205037195

大意翻译:

题目给了一个数组,要将这个数组的每一个元素都化为零,现在有两种操作,即:

  1. 将前面的数减一,后面的数加一(两个数不需要相连),不消耗积分
  2. 将后面的数减一,钱面的数加一(两个数不需要相连),需要消耗一积分

解析

我们先来看第一个样例:

4
-3 5 -3 1

对于这个样例来说,首先我们收集了第一个值:-3,这个值只能通过后面的值来补齐,我们再看看第二个值:5,这个值可以为后面补齐5点,同样的,看第三个值:-3,因为我们前面已经有5了,所以这个-3可以被补齐为0,同时剩余的值变为2,后续的操作以此类推……

简化一下来说就是我们可以设置两个值, leftans,其中left用来储存没有消费的值,ans用来储存答案

当遇到正值的时候,我们我们将正值添加到left里面,当遇到负值的时候,优先消耗负值,如果负值依旧没有被消耗完,那么就将负值添加到ans里面

完成整个步骤之后,我们只需要输出ans就可以得到答案了,但是需要注意的是,因为数据比较大,我们需要优先使用long long型的数据

完整代码

/*
* ===============================================
* Filename: cfb.cpp
* Description: CODEFORCES DIV 2
* Website: https://grimoire.cn
* Copyright (c) 2020 Mr.Sen. All rights reserved.
* ===============================================
*/

#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long left = 0, ans = 0;
    int n, number;
    cin >> number;
    while (number--)
    {
        left = 0, ans = 0;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            long long x;
            scanf("%lld", &x);
            if (x < 0)
            {
                x += left;
                left = 0;
                // 优先消耗x的值
            }
            if (x < 0)
            {
                ans -= x;
                // 如果x的值还小于0的话
                // 那么就将负值添加到ans里面
            }
            else
            {
                left += x;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
Archives Tip
QR Code for this page
Tipping QR Code