CF 1443D Extreme Subtraction（貪心，構造）
樣例（x）：
8
15 16 17 19 27 36 29 33
結果（t1）
15 15 16 18 26 35 28 32
思路：我們可以把最左端和最右端當做兩個水龍頭，每個水龍頭流量的上限就是a[x].
我們通過貪心，我們儘可能的使用左邊的流量，例如樣例(x)，我們流到第二個點的時候，我們發現左邊的流量不可能在第二個點流出16單位流量，說明這個點需要右邊流量的補充，而且只需要補充1單位的流量，那有人會問，為什麼不多流過來一些呢，這裡就是貪心的想法，我左邊邊能完成的事就不勞煩你右邊，儘可能的使用左邊，不行的讓右邊來補充，這樣樣例(x)的數組就變成了結果（t1）的數組，當然，我們需要更新左邊能流過來的流量flow = min(flow, a[i])和記錄我們右邊已經流向左邊的流量d,因為右邊流過來了流量，那麼右邊的容量也就是剩餘還需要補充的流量需要減少，當我們繼續流向下一個點的時候，當前需要流過來的流量應該是a[now] -= d，d為右邊流過來的流量，如果a[now] < 0,說明這個點不能夠承載d的流量，否則繼續進行更新操作。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <queue> 5 6 using namespace std; 7 8 #define ll long long 9 #define pb push_back 10 #define lson(rt) (rt << 1) 11 #define rson(rt) (rt << 1 | 1) 12 #define fi first 13 #define se second 14 15 const int N = 3e4 + 10; 16 int a[N]; 17 18 void solve() 19 { 20 int _case = 0; 21 scanf("%d", &_case); 22 for(int o = 1; o <= _case; ++o) { 23 int n; 24 scanf("%d", &n); 25 for(int i = 1; i <= n; ++i) scanf("%d", a + i); 26 27 int flag = 1; 28 int d = 0; 29 int Min = a[1]; 30 for(int i = 2; i <= n; ++i) { 31 a[i] -= d; 32 if(a[i] < 0) flag = 0; 33 if(Min >= a[i]) Min = a[i]; 34 else { 35 d += a[i] - Min; 36 } 37 } 38 //for(int i = 1; i <= n; ++i) cout << a[i] << " "; 39 //cout << endl; 40 41 printf("%s\n", flag ? "YES" : "NO"); 42 } 43 } 44 45 int main(){ 46 47 solve(); 48 49 return 0; 50 }/* 51 8 52 15 16 17 19 27 36 29 33 53 */
