山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[Codeforces] C. Reorder the Array [Round #497]

問題

Problem - C - Codeforces

英語が分からなくて例題が分からなかった問題です。

f:id:yamakasa3:20180811002509p:plain

考え方

元の配列の要素よりも大きくなるように並び変えます。

例えば、1, 2, 3, 4 であれば、2, 3, 4, 1と並び替えれると元の要素よりも大きい要素の数は3となります。

どのように数え上げれば良いのかですが、初めに配列を昇順に並び替えます。

ここで配列のインデックスを l = 0 r = 1 とします。

 a[l] \lt a[r] のとき

カウントを増やし、 l = l + 1 r = r + 1 とします。

上記以外のとき

 r = r + 1 とします。

これらを r = N - 1 となるまで繰り返します。

コード

import java.util.Arrays;
import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        long a[] = new long[N];
        for(int i = 0; i < N; i++) {
            a[i] = scan.nextLong();
        }
        scan.close();
        if(N == 1) {
            System.out.println(0);
            System.exit(0);
        }
        Arrays.sort(a);
        int cnt = 0;
        int l = 0;
        int r = 1;
        while(r < N) {
            if(a[l] < a[r]) {
                cnt++;
                l++;
                r++;
            }else {
                r++;
            }
        }
        System.out.println(cnt);
    }
}