Code Forces Round #668(Div.2)
B. Array Cancellation
题目链接:https://codeforces.com/contest/1405/problem/B
题目原文:
大意翻译:
题目给了一个数组,要将这个数组的每一个元素都化为零,现在有两种操作,即:
- 将前面的数减一,后面的数加一(两个数不需要相连),不消耗积分
- 将后面的数减一,钱面的数加一(两个数不需要相连),需要消耗一积分
解析
我们先来看第一个样例:
4
-3 5 -3 1
对于这个样例来说,首先我们收集了第一个值:-3,这个值只能通过后面的值来补齐,我们再看看第二个值:5,这个值可以为后面补齐5点,同样的,看第三个值:-3,因为我们前面已经有5了,所以这个-3可以被补齐为0,同时剩余的值变为2,后续的操作以此类推……
简化一下来说就是我们可以设置两个值, left
和 ans
,其中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;
}
作者:NorthCity1984
出处:https://grimoire.cn/acm/cf668.html
版权:本文《Code Forces Round #668(Div.2)》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任
出处:https://grimoire.cn/acm/cf668.html
版权:本文《Code Forces Round #668(Div.2)》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任