【枚举】CF1706 C

Myth丶恋晨 2024-03-23 19:27 44阅读 0赞

**有人一道1400写了一个小时**

[Problem - C - Codeforces][]

题意：  
![24af41cf246b45db9ced0751c3617969.png][]

思路：

首先先去观察样例：

很显然，对于n是奇数的情况，只有一种情况，直接操作偶数位就好了

主要是没搞清楚n是偶数的情况

![078f8e21becf4a2a9bb9c83fd9a6f389.png][]

![82744ee171514432b63ef59a62c85d4e.png][]

其实有个小技巧，在模拟样例的时候特殊化成0和1会比较好看一点

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    using namespace std;
    
    const int N = 1e5 + 10;
    
    int h[N];
    
    int calc(int p) {
        if (h[p] > h[p - 1] && h[p] > h[p + 1]) return 0;
        else {
            return max({h[p - 1], h[p + 1]}) - h[p] + 1;
        }
    }
    void solve() {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i ++) {
            cin >> h[i];
        }
    
        int ans = 0;
        for (int i = 2; i < n; i += 2) {
            ans += calc(i);
        }
    
        int res = ans;
        if (n % 2 == 0) {
            for (int i = n - 2; i >= 2; i -= 2) {
                res -= calc(i);
                res += calc(i + 1);
                ans = min(ans, res);
            }
        }
        cout << ans << "\n";
    }
    signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int t = 1;
        cin >> t;
        while(t --) {
            solve();
        }
        return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1706/problem/C
[24af41cf246b45db9ced0751c3617969.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/3e4d9c4e071947acb65523b6b037dc29.png
[078f8e21becf4a2a9bb9c83fd9a6f389.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/fe81bb7ad114407c8ea1405991572da7.png
[82744ee171514432b63ef59a62c85d4e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/b60b41eee7f647899ce9965d9fb20255.png