【反悔贪心+二分答案+枚举】Educational Codeforces Round 149 (Rated for Div. 2) F. Editorial for Two

小咪咪 2024-03-16 09:24 90阅读 0赞

[Problem - F - Codeforces][]

题意：

给定一个长度为N的数列，问你所有长度为K的子序列中，将子序列分割成两部分，max(左半部分，右半部分）的最小值是多少

![89a2cdfff8d3460a88c911446edb7fc6.png][]

思路：

最小化最大值，我们去二分这个最大值

那么，接下来就是看是否存在所有长度为K的子序列中分割成两部分的max(左，右）<=mid，即去看这个子序列的长度有没有K

关于子序列，这里用反悔贪心

用堆预处理出前缀的子序列和后缀的子序列，然后枚举分割点就好了

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=3e5+10;
    const int mxe=3e5+10;
    
    int N,K;
    int a[mxn];
    
    bool check(int mid){
    	priority_queue<int> q1,q2;
    	vector<int> v1(N+1),v2(N+1);
    	int sum=0;
    	for(int i=1;i<=N;i++){
    		q1.push(a[i]);
    		sum+=a[i];
    		while(sum>mid){
    			int u=q1.top();
    			q1.pop();
    			sum-=u;
    		}
    		v1[i]=q1.size();
    	}
    	sum=0;
    	for(int i=N;i>=1;i--){
    		q2.push(a[i]);
    		sum+=a[i];
    		while(sum>mid){
    			int u=q2.top();
    			q2.pop();
    			sum-=u;
    		}
    		v2[i]=q2.size();
    	}
    	int cnt=v2[1];
    	for(int i=1;i<=N;i++){
    		if(i==N) cnt=max(cnt,v1[i]);
    		else cnt=max(cnt,v1[i]+v2[i+1]);
    	}
    	return cnt>=K;
    }
    void solve(){
    	cin>>N>>K;
    	int sum=0;
    	for(int i=1;i<=N;i++){
    		cin>>a[i];
    		sum+=a[i];
    	}
    	int l=0,r=sum,ans=0;
    	while(l<=r){
    		int mid=l+r>>1;
    		if(check(mid)){
    			ans=mid;
    			r=mid-1;
    		}else{
    			l=mid+1;
    		}
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - F - Codeforces]: https://codeforces.com/contest/1837/problem/F
[89a2cdfff8d3460a88c911446edb7fc6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/79ce1968559843aa9ab455bdc473a68b.png