样例（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 #include2 #include 3 #include 4 #include 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 o) { 23 int n; 24 scanf("%d", &n); 25 for(int i = 1; i "%d", a + i); 26 27 int flag = 1; 28 int d = 0; 29 int Min = a[1]; 30 for(int i = 2; i 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 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 */
Original: https://www.cnblogs.com/SSummerZzz/p/13924213.html
Author: SummerMingQAQ
Title: D.Extreme Subtraction（贪心，构造）【CF 1443】
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584293/
转载文章受原作者版权保护。转载请注明原作者出处！