Codeforces #311 Div2 C. Arthur and Table

CF#311に参加。
割とグダグダかと思ったけど、なんとか全完。
http://codeforces.com/contest/557/problem/C

問題

N個の脚がついた机がある。
各脚の長さはL[i]で、脚を切るのにかかるエネルギーはD[i]である。

ここでいくつかの脚を切り机を安定させたい。
机を安定させるには、机の脚の長さの過半数が同じ長さでかつ最長でなければならない。
必要な最小エネルギーを求めよ。

解法

ある長さPで机を安定させる場合を考える。
長さPの脚の数をQとすると、Pより長い脚全てと、P未満の長さの脚を最大(Q-1)個残して残りを消費エネルギーの小さい順に切り落とせばよい。

各脚の長さについて総当たりし、上記条件を満たす最小エネルギーを求めればよい。
max|D|が小さいので、短い脚の切り落とし順は、エネルギーの小さい順に求めていけば間に合うので、SegTreeなどは要らない。

int ND[202];
int L[101010],D[101010];
vector<int> DL[101010];
int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>L[i];
	FOR(i,N) {
		cin>>D[i];
		ND[D[i]]++;
		DL[L[i]].push_back(D[i]);
	}
	
	ll mi=1LL<<30;
	ll tot=0;
	int left=N;
	
	for(i=101000;i>=0;i--) if(DL[i].size()) {
		
		int rem=max(0,left - (int)(DL[i].size()*2-1));
		FORR(r,DL[i]) ND[r]--;
		ll tot2=0;
		for(j=1;j<=200 && rem;j++) {
			x=min(rem,ND[j]);
			tot2 += x*j;
			rem-=x;
		}
		mi=min(mi,tot+tot2);
		
		FORR(r,DL[i]) tot+=r;
		left -= DL[i].size();
	}
	
	cout<<mi<<endl;
	
}

まとめ

Dが大きかったらちょっとめんどくさそう。