Mix the colors [CodeChef March Challenge 2018 Div1 A]

https://www.codechef.com/MARCH18A/problems/MIXCOLOR

N要素の配列Aがある。
「x番目の数をy番目に足す」という操作を繰り返して全ての数が異なるようにしたい。
最小何回操作すればよいか。

解法

https://www.codechef.com/viewsolution/17597887

最適戦略を考えてみると、数がダブっている数は現時点の最大値を足すことで、足された要素は全ての最大値となり、かつユニークな数となる。
次のダブっている数をユニークにするときにも、その最大値を足すことで、またそのダブっている数が最大値となり、ユニークな数となる。
よって、ダブっている数の個数分だけ操作することで全ての数が異なるようにできる。
これは明らかに下界なので、最適。
なので、ダブっている数の個数を数えて答えると、それが操作の最小回数。

int N, A[101010];
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N);
 
    int ans = 0;
    rep(i, 0, N - 1) if (A[i] == A[i + 1]) ans++;
    cout << ans << endl;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}