codeforces 1442 A. Extreme Subtraction（贪心，构造）

样例（x）：

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  */

巴特西

codeforces 1442 A. Extreme Subtraction（贪心，构造）

最新文章

热门文章