SRM530 easy(250) - avrmicom @ ウィキ

SRM530 easy(250)

2012/1/25
77.91 points

問題概要

瓶の中のボールを移し替えて、ボールの個数が昇順になるようにする。このときの最悪の手順数（移動個数）を求める問題。
問題では昇順に並べ替えられた後の状態が入力として与えられる。

Examples

{0, 2, 5}
Returns: 5
This is the example from the problem statement. No sequence is worse than S = {2, 5, 0}. There are two other sequences S such that Gogo will make exactly 5 moves when producing T = {0, 2, 5}, namely {5, 0, 2} and {5, 2, 0}.

解法

配列の両端の差をとり、また、その内側の両端の差をとり、。。。を繰り返して、それらの和をとる。
これでできた。

解答

#include <vector>
#include <iostream>
using namespace std;

class GogoXBallsAndBinsEasy{
public:
	int solve(vector <int> T){
		int value=0;
		for(int i=0; i<T.size()/2; i++){
			value += T[T.size()-1-i] - T[i];
		}
		return value;
	}
};