SRM646div1easy:TheConsecutiveIntegersDivOne
前に同じ発想を使う問題を解いたので近い発想には至れたが、なんとなくコードを提出した後にちゃんとした証明を思いついた。
問題:http://community.topcoder.com/stat?c=problem_statement&pm=13625&rd=16278
解法:まず数列をソートする。一番大きい数を決めると、他の数は自動的に決まる。このようにして数が決まった時、どこに数を集めたら操作回数が一番小さくなるかを考える。最終的に数を[x,x+1,...,x+k-1]に集めるとすると、操作回数は|x-a1|+|(x+1)-a2|+...+|(x+k-1)-ak| = |x-a1|+|x-(a2-1)|+...+|x-(ak-k+1)|となる。これを最小にするxの候補として、x=a1,a2-1,...,ak-k+1が挙げられるので、これらを全部調べる。
以下ソースコード
const int INF = 1e9; class TheConsecutiveIntegersDivOne { public: int find(vector <int> numbers, int k) { if (k == 1) return 0; int n = numbers.size(); sort(numbers.begin(), numbers.end()); int ret = INF; for (int i = 0; i < n; i++) { // numbers[i]が一番でかい if (i >= k-1) { vector<int> a; for (int j = i; j >= i-k+1; j--) { a.push_back(numbers[j]); } int mindiff = INF; for (int j = 0; j < k; j++) { int diff = 0; int x = a[j]; for (int l = 0; l < k; l++) { diff += abs(x-(l-j)-a[l]); } mindiff = min(mindiff, diff); } ret = min(ret, mindiff); } } return ret; } };