Codeforces #204 Div1. A. Jeff and Rounding

最近CFの問題を解いてここで記録するペースが開催ペースに間に合っていないので、開催後はできるだけ早めに書くようにする。
このCF204はA,Bも解けてまさかのEも解き、そこそこの順位が解けた。
Cも後で解けたしなかなか良い成績でした。久々に2ケタ順位だし。
http://codeforces.com/contest/351/problem/A

問題

2N個の正の実数列A[i]が与えられる。
このうちN個をceil(A[i])、N個をfloor(A[i])に置き換える。
置換前後で数列の総和の差分の絶対値を最小化せよ。

解法

ceilをとったときとfloowをとったときの差分を考えてみる。
floorをとると、置換前後の差分はA[i]-floor(A[i])。
ceilをとると、置換後の差分はA[i]-ceil(A[i])=A[i]-1-floor(A[i]) ただし、A[i]が整数のときは"-1"がつかない。

こう考えると、総和の差分はA[i]-floor(A[i])の和をとり、N回ceilをとって-1したものになる。
A[i]が整数の数に応じて、-1をとれる数が変わるので、-1を0～N回とって最小値を答える。

なお、最初のA[i]の整数部は不要なので、先に消してしまった上で小数点以下を1000倍して整数化し、処理を楽にしている。

int N;
int A[5000];

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>N;
	FOR(i,2*N) {
		double d;
		cin>>d;
		d=d*1000+0.1;
		A[i]=((int)d)%1000;
	}
	sort(A,A+2*N);
	int tot=0,n=0;
	FOR(i,2*N) tot += A[i];
	FOR(i,2*N) if(A[i]!=0) n++;
	int res=1000000000;
	FOR(i,N+1) {
		if(i>n) continue;
		if(i<n-N) continue;
		res=min(res,abs(tot-i*1000));
	}
	
	_P("%d.%d%d%d\n",res/1000,(res/100)%10,(res/10)%10,res%10);
	
	return;
}

まとめ

ceilとfloorの特徴を使った面白い問題。