題意：給你n個高度，再給你1~n每種高度的數量，已知高度連續的3~5個能消去，問你所給的情況能否全部消去；例：n = 4，給出序列1 2 2 1表示高度1的1個，高度2的2個，高度3的2個，高度4的1個。那么我打出1 1 1（高度1 2 3），1 1 1（高度2 3 4）剛好打完。

思路：對于差分數組我們知道，如果我們對區間L,R加1，那么d[L] += 1, d[R + 1] -= 1，我們可以想象這個序列是由0序列不斷進行區間+1操作得到。我們打出差分數組，從左到右遍歷，如果遇到正數，那么我們就往右找負數把他消掉，如果這個負數和正數距離小于3那么顯然無法構成，其他都可以（大于5時我們可以證出這個距離可以用3 4 5表示）；如果遇到負數顯然沒有正數和他匹配，也不行。

代碼：

#include<set> #include<map> #include<stack> #include<cmath> #include<queue> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> typedef long long ll; using namespace std; const int maxn = 200000 + 10; const int seed = 131; const ll MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; ll a[maxn], d[maxn]; int main(){int T, n, Case = 1;scanf("%d", &T);while(T--){scanf("%d", &n);a[0] = 0;for(int i = 1; i <= n; i++){scanf("%lld", &a[i]);d[i] = a[i] - a[i - 1];}d[n + 1] = -a[n];int flag = 0;int j = 2;for(int i = 1; i <= n; i++){if(d[i] < 0) flag = 1;while(j <= n + 1 && d[i] > 0){if(d[j] < 0){if(j - i < 3) flag = 1;if(d[j] + d[i] < 0){d[j] += d[i];d[i] = 0;}else{d[i] += d[j];d[j] = 0;j++;}}else j++;}if(d[i] > 0) flag = 1;if(flag) break;}printf("Case #%d: ", Case++);if(flag) printf("No\n");else printf("Yes\n");}return 0; }

?

轉載于:https://www.cnblogs.com/KirinSB/p/10010010.html

總結

以上是生活随笔為你收集整理的Gym 101775J Straight Master（差分数组）题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。