Codeforces #852 : Div2 E. Velepin and Marketing

なんか手間取った。
https://codeforces.com/contest/1793/problem/E

問題

N人の人がおり、何冊かの本を読む。
各人iはA[i]人以上同じ本を読んでいると満足する。
ただし、どの本も最低1人は読んでなければいけない。

以下のクエリに答えよ。

• 本がK冊ある場合、最大何人満足できるか。

解法

前処理として、「i人満足する場合何冊以下の本なら良いか」を求めておこう。
二分探索でも良いし、SegTreeを使ってiの小さい順に総当たりしても良い。

int N;
int A[303030];
int Q;
int K;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=-(1<<30);
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;
int dp[302020];
int dpK[302020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	
	st.update(0,0);
	FOR(i,N) {
		if(A[i]<=i+1) {
			dp[i+1]=1+st.getval(0,i+1-A[i]+1);
			x=max(0,dp[i+1]+N-(i+1));
			st.update(i+1,dp[i+1]);
		}
		else {
			x=N-A[i]+1;
		}
		dpK[x]=i+1;
	}
	
	for(i=N-1;i>=1;i--) dpK[i]=max(dpK[i],dpK[i+1]);
	
	cin>>Q;
	while(Q--) {
		cin>>K;
		cout<<dpK[K]<<endl;
	}
}

まとめ

なんか問題文読みにくいな。