题目大意:
有一个非负整数序列 \(A\),定义序列 \(D\) 是序列 \(A\) 的绝对值差分序列,问给定序列 \(D\),能否求出唯一的序列 \(A\),若不能,输出 \(-1\),否则输出序列 \(A\)。
题目分析:
因为属于差分序列,所以我们不难得出序列 \(D\) 的前缀和序列 \(S\) 就是序列 \(A\) 的一种。
那么不能得出唯一解得情况就很好想了,如果 \(S_{i-1}+(-D_i) \ge 0\),那么就说明有多个序列 \(A\),理由如下:
因为 \(D_i\) 是 \(A_{i-1}-A_i\) 的绝对值,所以原差分序列中 \(D_i\) 的位置可正可负,如果 \(S_{i-1}+(-D_i) < 0\),则说明了原差分序列上 \(D_i\) 的位置肯定为非负整数(因为序列 \(A\) 是由非负整数构成的),反之则说明原差分序列上 \(D_i\) 的位置的正负性不影响序列 \(A\) 是一个非负整数序列,故此时序列 \(A\) 有多种。
代码实现:
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n;
int d[200] = {};
cin >> n;
for (int i = 1; i <= n; i++)
cin >> d[i];
bool inc = 1;
int a[200] = {};
a[1] = d[1];
for (int i = 2; i <= n; i++)
a[i] = a[i - 1] + d[i];
for (int i = 2; i <= n; i++) {
if (a[i - 1] >= d[i] && d[i]) {
cout << -1 << endl;
inc = 0;
break;
}
}
if (!inc)
continue;
for (int i = 1; i <= n; i++)
cout << a[i] << ' ';
cout << endl;
}
return 0;
}
标签:CF1739B,非负,int,题解,差分,整数,序列
From: https://www.cnblogs.com/larry76/p/17127344.html