UnKoder #04 : Book Stacks

ARCのB位で出そう。
https://www.hackerrank.com/contests/unkoder-04/challenges/book-stacks

問題

N個の本の山があり、それぞれA[i]冊積まれている。
１回の処理で以下の何れかを行える。

• どこかの山の最上位の本を１冊読む。
• どこかの山の最上位の本を他の山の最上位に積む。

全ての本を読むのにかかる最小処理回数を求めよ。

解法

以下のアプローチを取ればよい。

• 最小の山から、1冊を残して本を他の山に動かす。
• 最小の山に残った1冊を読む
• 他の山から、1冊を残して読む→最小の山に積みなおす、を繰り返す。

Aが昇順にソートされているとすると、上記処理回数はとなる。

int N;
int A[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	
	int sum=A[0]+(A[0]-1)*2;
	for(i=1;i<N;i++) sum += A[i]+(A[i]-1);
	cout<<sum<<endl;
}

まとめ

シンプルな問題設定でいいね。