Codeforces #423 Div1 B. High Load

これは割とあっさり。
http://codeforces.com/contest/827/problem/B

問題

整数N,Kが与えられる。
N頂点の木を成す無向グラフで、葉となる頂点がK個あるようなもののうち、葉同士の距離の最大値が最小となるものを構築せよ。

解法

まずは1点の周りにK個の葉からなる(K+1)頂点のグラフを作ろう。
余った頂点があれば順に葉までの距離を1つずつ長くしていけばよい。

int N,K,L;
int V[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	FOR(i,K) V[i]=1;
	FOR(i,N-(K+1)) V[i%K]++;
	sort(V,V+K);
	
	_P("%d\n",V[K-1]+V[K-2]);
	int nex=2;
	FOR(i,K) {
		int pre=1;
		FOR(j,V[i]) {
			_P("%d %d\n",pre,nex);
			pre=nex;
			nex++;
		}
	}
}

まとめ

コードは短いけど、ちょっと迷った。