D. Extreme Subtraction(差分)_资讯

D. Extreme Subtraction(差分)

创始人

2024-01-29 21:26:22

0次

Problem - 1443D - Codeforces

给你一个由n个正整数组成的数组a。

你可以随意使用下面的操作：选择任何一个1≤k≤n的整数，做两件事中的一件。

将数组中的前k个元素递减1。
将数组的最后k个元素递减1。
例如，如果n=5，a=[3,2,2,1,4]，那么你可以对其应用以下操作之一（下面没有列出所有可能的选项）。

从数组的前两个元素开始递减。在这个操作之后a=[2,1,2,1,4]。
从数组的最后三个元素中递减。此操作后a=[3,2,1,0,3]。
从数组的前五个元素中递减。此操作后a=[2,1,1,0,3]。
确定是否有可能通过应用一定数量的操作使数组的所有元素都等于零。

输入
第一行包含一个正整数t（1≤t≤30000）--测试案例的数量。接着是t个测试用例。

每个测试用例的第一行包含一个整数n（1≤n≤30000）--数组中元素的数量。

每个测试用例的第二行包含n个整数a1...an（1≤ai≤106）。

所有测试用例的n之和不超过30000。

输出
对于每个测试用例，在一个单独的行上输出。

是，如果有可能通过应用一定数量的操作使数组的所有元素等于零。
NO，否则。
YES和NO这两个词中的字母可以在任何情况下输出。

例子
Input
4
3
1 2 1
5
11 7 9 6 8
5
1 3 1 3 1
4
5 2 1 10
输出
是
是
没有
是

题解:
根据差分数组的性质,如果数组全为0,那么差分数组的值肯定也全为0

题目给了我们两步操作

一种相当于d[i]-1 d[k+1]+1可以把为负数的差分数组值变增大

另一种相当于d[i]-1 d[n+1]+1 可以把为整数的差分数组的值减小

对于所以大于0的差分数组的值,可以通过操作2实现,并且没有限制,所以无需考虑

关键使为负数的差分数组的值,我么可以发现只要d[1]足够大,就可以把所有的为负数的差分数组的值变为0,

#include
#include
#include
#include
#include
#include
#include
using namespace std;
long long sum[200050];
void solve()
{int n;cin >> n;long long s = 0;for(int i = 1;i <= n;i++){cin >> sum[i];int k = sum[i] - sum[i-1];if(k < 0){s -= k;}}if(s <= sum[1]){cout<<"YES\n";}else{cout<<"NO\n";}
}
int main()
{int t = 1;cin >> t;while(t--){solve();}
}
//
//abcdef
//babcdef
//1110011//

上一篇：“幂等”不等于“分布式锁”，也不得不考虑返回值

下一篇：限时开源，来自大佬汇总的Kafka限量笔记，绝对不会后悔！

D. Extreme Subtraction(差分)

相关内容

热门资讯