A. Directional Increase -前缀和与差分理解 + 思维

本文主要是介绍A. Directional Increase -前缀和与差分理解 + 思维，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

分析

观察指针移动的性质，可以发现每一段都是从起点走到终点，在原路返回，这样每一段也就表示，在起点处加一，在终点处减一，形成了很明显的差分结构，思考能否构造出a数组的关键就是他的前缀和数组b的b[n]必须等于0，并且每一个$b_i$都不能小于0，因为起点大于0，终点小于0，所有数都应该是大于等于0的，在某一个下标一旦前缀和数组元素等于0，代表开始原路返回，这是走过最长的一段，那么后面所有的前缀和元素都必须是0.

代码

#include <bits/stdc++.h>using namespace std;
using ll = long long;void solve() {int n;cin >> n;vector<ll> a(n + 1);for(int i = 1; i <= n; i ++) {cin >> a[i];a[i] += a[i - 1];}if(a[n] != 0) {cout << "No\n";return ;}int flag = 0;for(int i = 1; i <= n; i ++) {if(a[i] < 0) {flag = 1;break;}}int cnt = 0;for(int i = 1; i <= n; i ++) {if(a[i] == 0) cnt = 1;else {if(cnt == 1) {flag = 1;break;}}}if(flag == 1) cout << "No\n";else cout << "Yes\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while(T --) {solve();}
}

这篇关于A. Directional Increase -前缀和与差分理解 + 思维的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---