CF 1616D. Keep the Average High-有解無憂

傳送門
 1 /*
 2 思路:把 a1 + a2 + ... + an >= x * (r - l + 1)  
 3         ===>  a1 + a2 + ... + an - x * (r - l + 1) >= 0
 4     可以等價為對于每個(ai - x) 得到新的ai，則題目變為對于任意區間[l, r], al + ... + ar >= 0.
 5     
 6     我們先考慮： ai分布為  + - + - + - ...  (ai正負交替出現)
 7      
 8     對于 ( a1(-) a2(+) a3(-) ) 這相鄰的三個數， 
 9     如果a1 + a2 < 0 和 a2 + a3 < 0只滿足其一，則容易想到把滿足等式的那個ai(-)不取.
10     如果兩個都滿足，則需要用到貪心的思想，我們應該不取中間的a2，因為a2不取，
11     使得我們可能可以取a1, a3; 如果是不取a1, a3則只有a2可以取.
12     
13     如果上述兩個等式都不成立，而 a1 + a2 + a3 < 0，則我們貪心的讓a3(-)不取，這樣對于后面的取與不取有意義
14     
15     當然，對于ai(-)如果已經確定是不取的情況得判定
16     
17     其他的就是一般的情況   - + - + + + - + + - - -
18     我們就可以知道，只需要對于ai(+)來判斷左右的情況即可.
19     對于ai(-)則只需判斷前面一個元素是不是負數,是不是不取來判斷自己是不是不取,因為兩個(-)一定是不滿足題意的.
20     
21     從最小的相鄰的區域滿足可以得到整體的滿足.
22 */
23 
24 
25 
26 
27 #include <bits/stdc++.h>
28 using namespace std;
29 
30 #define ll long long
31 #define ANS cout<<"ans: ";
32 
33 const int N = 1e6 + 10;
34 
35 int a[N];
36 struct node {
37     int v;
38     int w;//改數取不取
39 };
40 int n;
41 
42 inline bool check (int x, int id)
43 {
44     if(id == 0) return x - 1 >= 0;
45     else return x + 1 < n;
46 }
47 
48 void solve ()
49 {
50     int T;
51     cin >> T;
52     while(T --) {
53 
54         cin >> n;
55         for(int i = 1; i <= n; i ++) cin >> a[i];
56 
57         int x;
58         cin >> x;
59 
60         vector<node > vn;
61         for(int i = 1; i <= n; i ++) vn.push_back({a[i] - x, 1});
62 
63         int tot = 0;
64         for(int i = 0; i < n; i ++) {
65             if(vn[i].v >= 0) {
66                 int l, r;
67                 l = r = 0;
68                 if(check(i, 0) && vn[i - 1].v < 0 && vn[i - 1].w == 1 && vn[i].v + vn[i - 1].v < 0) l = 1;
69                 if(check(i, 1) && vn[i + 1].v < 0 && vn[i + 1].w == 1 && vn[i].v + vn[i + 1].v < 0) r = 1;
70                 if(l + r == 2) tot ++;
71                 else if(l == 1) tot ++, vn[i - 1].w = 0;
72                 else if(r == 1) tot ++, vn[i + 1].w = 0;
73                 else if(l + r == 0) {
74                     int sum = vn[i].v;
75                     if(check(i, 0) && vn[i - 1].v < 0 && vn[i - 1].w == 1) sum += vn[i - 1].v;
76                     if(check(i, 1) && vn[i + 1].v < 0 && vn[i + 1].w == 1) sum += vn[i + 1].v;
77                     if(sum < 0) tot ++, vn[i + 1].w = 0;
78                 }
79             } else if(vn[i].v < 0 && vn[i].w == 1) {
80                 if(check(i, 0) && vn[i - 1].v < 0 && vn[i - 1].w == 1) tot ++, vn[i].w = 0;
81             }
82         }
83 
84         ANS;
85         cout << n - tot << endl;
86     }
87 }
88 
89 int main()
90 {
91     solve();
92 
93     return 0;
94 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/404285.html
標籤：其他
上一篇：華為應用內評論測驗要求
下一篇：再見 Dockerfile，擁抱新型鏡像構建技術 Buildpacks