mayoko’s diary

プロコンとかいろいろ。

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;
    }
};