C - BBuBBBlesort! AtCoder Grand Contest 003

C - BBuBBBlesort!

問題概略

長さNの数列を3つか２つ選び反転する。2つの最小操作回数は

制約

• $1\leqq N\leqq {10}^5$
• $0\leqq A_i\leqq {10}^9$
• $i\ne j$ ならば $A_i\ne A_j$
• 入力はすべて整数である。

解法

3つの数を反転する操作を使うと偶数項、奇数項で、自由に動かせる。

ここで、動かす距離が偶数の物は3だけで出来るが、奇数のものは偶数個存在して、うまく動かせば一回で２つを設置できる。

類題

座圧

 public static void main(String[] args)
    {
        //longを忘れるなオーバーフローするぞ
        N = sc.nextInt();
        A = sc.nextIntArray(N);
        int[] B = A.clone();
        Arrays.sort(B);
        for (int i = 0; i < N; i++)
        {
            A[i] = lowerBound(B, A[i]);
        }
        long cou = 0;
        long res = 0;
        for (int i = 0; i < N; i++)
        {
            if (Math.abs(A[i] - i) % 2 == 1)
            {
                res++;
            }
        }

        System.out.println(res/2);
    }