【分类讨论】CF1674 E

墨蓝 2024-03-24 00:38 81阅读 0赞

[Problem - E - Codeforces][]

题意：

![6ee648e7f87141c8ad84d1f4bbe361ce.png][]

![66628458d20640e5a66258ff8ed6b177.png][]

思路：

样例：

![c866ab2a375f45f89ec2f9f6edaafe49.jpeg][]

这种分类讨论的题，主要是去看答案的最终来源是哪几种情况，这几种情况得不重不漏

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    constexpr int N = 2e5 + 10;
    constexpr int mod = 998244353;
    
    int n;
    int a[N];
    
    void solve() {
    	std::cin >> n;
    	for (int i = 1; i <= n; i ++) {
    		std::cin >> a[i];
    	}
    
    	int ans = 1e9;
    	for (int i = 2; i <= n; i ++) {
    		int u = a[i - 1], v = a[i];
    		if (u > v) std::swap(u, v);
    		if (v > 2 * u) {
    			ans = std::min(ans, (v + 2 - 1) / 2);
    		}else {
    			ans = std::min(ans, (u + v + 3 - 1) / 3);
    		}
    	}
    
    	for (int i = 1; i <= n - 2; i ++) {
    		int u = a[i];
    		int v = a[i + 2];
    		if (u > v) std::swap(u, v);
    		if (u % 2 == 1 && v % 2 == 1) {
    			ans = std::min(ans, u / 2 + v / 2 + 1);
    		}
    	}
    
    	std::sort(a + 1, a + 1 + n);
    	ans = std::min(ans, (a[1] + 1) / 2 + (a[2] + 1) / 2);
    
    	std::cout << ans << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
    
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - E - Codeforces]: https://codeforces.com/contest/1674/problem/E
[6ee648e7f87141c8ad84d1f4bbe361ce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/0e48320eecf04ee18e76dd5effe2823a.png
[66628458d20640e5a66258ff8ed6b177.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/f517e23ab1fe41308153d1be8e451a24.png
[c866ab2a375f45f89ec2f9f6edaafe49.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/c465c251e078461fa3ac579e2c904918.png