読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #228 Div1. A. Fox and Box Accumulation

Codeforces

ABC解けてChallengeも稼げていい感じ、と思ったらBをミスで落とし、Cはそもそもアプローチミスで落としてひどい結果に。
CF Div1回で3連敗している…。
http://codeforces.com/contest/388/problem/A

問題

N個の段ボールがある。
各段ボールには強度が設定されており、上にその強度の数分だけ段ボールを乗せることができる。

N個の段ボールを積み重ねていくつかの山を作りたい。
山の数の最小数はいくつか。

解法

なんか見たことあるなーと思ったらこれだね。
C: 積み重ね - AtCoder Regular Contest #006 | AtCoder

段ボールを重ねる順は自由なので、強度が弱い順に上から決めていこう。
強度が弱い順に段ボールを見て、すでにある山のうち下に段ボールを置ける山があれば、既存の山の下に配置していく。
置ける山がなければ、新たな山を作る、を繰り返していけばよい。

int N;
int X[105];
int NN[105];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>X[i];
	sort(X,X+N);
	FOR(i,N) {
		for(x=0;x<=X[i];x++) {
			if(NN[x]) {
				NN[x]--;
				NN[x+1]++;
				break;
			}
		}
		if(x==X[i]+1) NN[1]++;
	}
	int r=0;
	FOR(i,102) r+=NN[i];
	_P("%d\n",r);
	
}

まとめ

本番は強度の強い順に取り組んでしまい時間をロスした。

広告を非表示にする