【贪心+二分】CF1791G2

柔光的暖阳◎ 2024-03-23 23:39 88阅读 0赞

[Problem - 1791G2 - Codeforces][]

题意：

![1207a1f598e74fa39c4b7b9aff9f9e40.png][]

![19d1d7d6f1f3417097f2fc7886dd733d.png][]

思路：

首先，模拟一下样例发现，第一次传送之后，每次传送的贡献都是独立的，每次的贡献都是

min(ai + i, ai + n - i + 1)，因此根据这个贪心即可

贪心无非两种写法：排序 or 堆，这里排序即可

按贡献 min(ai + i, ai + n - i + 1) 排序之后，我们发现，第一个传送门是什么不确定

我就想到了这里，这里我直接猜测第一个传送门一定是ai + i最小的那个，但是这个结论是错的

那么就回溯一下思路，思考一下一般情形，我们只需要枚举这个位置，然后把传送点个数取最大即可

那么问题就变成，假设我们第一个传送这个位置，怎么快速计算可以传送的传送门个数

那么直接在排序后的数组上操作即可，看最多延伸到这个数组的哪个长度

注意到这个长度具有单调性，当长度足够长时，钱就不够，足够短时钱够

我们考虑二分这个长度，看剩余的钱是否足够即可

注意要挖去第一次传送门

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    constexpr int N = 2e5 + 10;
    constexpr int M = 2e5 + 10;
    constexpr int mod = 998244353;
    
    int n, c;
    int a[N], s[N];
    
    int check(int c, int x, int id) {
    	int l = 1, r = n;
    	int ans = -1;
    	while(l <= r) {
    		int mid = l + r >> 1;
    		if (s[mid] - (mid >= id ? x : 0) <= c) {
    			ans = mid + (mid >= id ? -1 : 0);
    			l = mid + 1;
    		}else {
    			r = mid - 1;
    		}
    	}
    	return ans == -1 ? 0 : ans;
    }
    void solve() {
    	std::cin >> n >> c;
    	for (int i = 1; i <= n; i ++) {
    		s[i] = 0;
    		std::cin >> a[i];
    		s[i] = std::min(a[i] + i, a[i] + n - i + 1);
    	}
    
    	std::sort(s + 1, s + 1 + n);
    
    	std::map<int,int> mp;
    	for (int i = 1; i <= n; i ++) {
    		mp[s[i]] = i;
    		s[i] += s[i - 1];
    	}
    
    	int ans = 0;
    	for (int i = 1; i <= n; i ++) {
    		if (c < a[i] + i) continue;
    		ans = std::max(ans, check(c - a[i] - i, std::min(a[i] + i, a[i] + n - i + 1), mp[std::min(a[i] + i, a[i] + n - i + 1)]) + 1);
    	}
    
    	std::cout << ans << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
    	std::cin >> t;
    
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - 1791G2 - Codeforces]: https://codeforces.com/problemset/problem/1791/G2
[1207a1f598e74fa39c4b7b9aff9f9e40.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/58123f7cb97342eb8f7b9140642e1259.png
[19d1d7d6f1f3417097f2fc7886dd733d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/efa2f608b85e440cb6d759b3071a5b74.png