Codeforces ECR #149 : F. Editorial for Two

本番妙にあっさり解いてるな。
https://codeforces.com/contest/1837/problem/F

問題

N要素の整数列Aと、整数Kが指定される。
AのうちK要素からなる部分列を作ったとする。
この部分列を前半後半に分けたとき、それぞれの和の最大値を最小化せよ。

解法

解Xを二分探索しよう。
f(n) := Aのprefix n個のうち、和がX以下となる要素数の最大値
g(n) := Aのsuffix n個のうち、和がX以下となる要素数の最大値

とすると、f(i)+g(N-i)≧Xとなるiがあればよいことになる。
f(n), g(n)はpriority queueなど使えば容易に計算できる。

int T,N,K;
int A[303030];

int B[303030];
int hoge(ll v) {
	priority_queue<int> Q;
	ll sum=0;
	int i;
	FOR(i,N) {
		sum+=A[i];
		Q.push(A[i]);
		while(sum>v) {
			sum-=Q.top();
			Q.pop();
		}
		if(Q.size()>=K) return K;
		B[i+1]=Q.size();
	}
	sum=0;
	while(Q.size()) Q.pop();
	
	int ma=B[N];
	for(i=N-1;i>=0;i--) {
		sum+=A[i];
		Q.push(A[i]);
		while(sum>v) {
			sum-=Q.top();
			Q.pop();
		}
		ma=max(ma,B[i]+(int)Q.size());
		if(ma>=K) return K;
	}
	return ma;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(i,N) cin>>A[i];
		
		ll ret=1LL<<50;
		for(i=49;i>=0;i--) if(hoge(ret-(1LL<<i))>=K) ret-=1LL<<i;
		cout<<ret<<endl;
		
	}
}

まとめ

なんでこれ6問回のボス問なんだろ。