Codeforces Round #668 (Div. 2) B

B. Array Cancellation

Description

给定一个有 $n$ 个整数的数组 $a$

每次都可以选择任意两个不同的 $i$ 和 $j$ ，进行如下操作

操作A： $a[i]--;a[j]++;$

操作B： $a[i]++;a[j]--;$

其中操作A可以无限免费执行，而操作B每次需要消耗一个金币。现请求出最少需要多少个金币才能使数组 $a$ 中各项归零

题目保证 $\sum_{i=1}^n a_i=0$

Input

第一行一个整数 $t$ 代表组数

之后每一组由两行构成，第一行为整数 $n$ 表示该组有 $n$ 个整数，第二行为 $n$ 个整数

Output

一个整数代表最少需要的金币个数

Analysis

太久没做题了，遇到这个题目一开始还有些没有头绪

我个人认为比较容易想到的做法是这样

从前向后考虑数列第一项，若第一项小于 $0$ 则必然这个数对答案的贡献就是其相反数（因为这个数只能通过操作B来归零），若其大于 $0$ 则其就可以允许之后的负数在上升的时候可以使用其归零所留下了富余值

定义两个变量记为 $lef$ 与 $ans$ 分别代表富余值与答案

我们通过一个样例来具体说明，如

4
-3 5 -3 1

4
-3 5 -3 1

4
-3 5 -3 1

$a_1$ 归零需要对答案产生 $3$ 的贡献 $lef=0,ans=3$

$a_2$ 归零可以允许之后的负数上升 $5$ $lef=5,ans=3$

$a_3$ 归零可以利用 $lef$ 故不对答案产生贡献 $lef=2,ans=3$

$a_4$ 归零不对答案产生贡献

故答案为 $3$

更加复杂的样例如

7
-5 7 -6 -4 17 -13 4

7
-5 7 -6 -4 17 -13 4

7
-5 7 -6 -4 17 -13 4

$a_1$ 归零需要对答案产生 $5$ 的贡献 $lef=0,ans=5$

$a_2$ 归零可以允许之后的负数上升 $7$ $lef=7,ans=5$

$a_3$ 归零可以利用 $lef$ 故不对答案产生贡献 $lef=1,ans=5$

$a_4$ 归零对答案产生 $3$ 的贡献 $lef=0,ans=8$

$a_5$ 归零可以允许之后的负数上升 $17$ $lef=17,ans=8$

$a_6$ 归零可以利用 $lef$ 故不对答案产生贡献 $lef=4,ans=8$

$a_7$ 归零不对答案产生贡献

故答案为 $8$

Accepted Code

/*
 * @Author       : Gehrychiang
 * @LastEditTime : 2020-09-07 10:11:40
 * @Website      : www.yilantingfeng.site
 * @E-mail       : gehrychiang@aliyun.com
 * @ProbTitle    : Array Cancellation
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class T>
void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
template <class T>
void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const long long &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
ll a[100005];
int main()
{
    int t;
    _R(t);
    while (t--)
    {
        int n;
        _R(n);
        for (int i = 0; i < n; i++)
        {
            _R(a[i]);
        }
        ll lef = 0;
        ll ans = 0;
        for (int i = 0; i < n; i++)
        {
            if (a[i] < 0)
            {
                a[i] += lef;
                lef = 0;
            }
            if (a[i] < 0)
            {
                ans += -a[i];
            }
            else
            {
                lef += a[i];
            }
        }
        _W(ans);
        _W("\n");
    }

    return 0;
}

/*
* @Author : Gehrychiang
* @LastEditTime : 2020-09-07 10:11:40
* @Website : www.yilantingfeng.site
* @E-mail : gehrychiang@aliyun.com
* @ProbTitle : Array Cancellation
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class T>
void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
template <class T>
void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const long long &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
ll a[100005];
int main()
{
int t;
_R(t);
while (t--)
{
int n;
_R(n);
for (int i = 0; i < n; i++)
{
_R(a[i]);
}
ll lef = 0;
ll ans = 0;
for (int i = 0; i < n; i++)
{
if (a[i] < 0)
{
a[i] += lef;
lef = 0;
}
if (a[i] < 0)
{
ans += -a[i];
}
else
{
lef += a[i];
}
}
_W(ans);
_W("\n");
}
return 0;
}

/*
 * @Author       : Gehrychiang
 * @LastEditTime : 2020-09-07 10:11:40
 * @Website      : www.yilantingfeng.site
 * @E-mail       : gehrychiang@aliyun.com
 * @ProbTitle    : Array Cancellation
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class T>
void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
template <class T>
void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const long long &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
ll a[100005];
int main()
{
    int t;
    _R(t);
    while (t--)
    {
        int n;
        _R(n);
        for (int i = 0; i < n; i++)
        {
            _R(a[i]);
        }
        ll lef = 0;
        ll ans = 0;
        for (int i = 0; i < n; i++)
        {
            if (a[i] < 0)
            {
                a[i] += lef;
                lef = 0;
            }
            if (a[i] < 0)
            {
                ans += -a[i];
            }
            else
            {
                lef += a[i];
            }
        }
        _W(ans);
        _W("\n");
    }

    return 0;
}