欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #497 (Div. 2) ---- C Reorder the Array

程序员文章站 2022-06-04 08:28:16
...

Codeforces Round #497 (Div. 2) ---- C Reorder the Array

给我们一些数字,我们把这个数字重新排列,那么会有一些位置的数大于这个位置上原来的数字,寻找这样的位置最多有多少。

有一种做法就是排序-贪心,最大的数优先放在比他小的最大的数字上

这里有一种方法,统计最大的出现过的数的次数cnt,n - cnt即可。

代码简单,第一种做法的代码,和第二种的证明,坑先留着一下吧。

#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
int main(){
    int n,num,ans = 0;
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> num;
        mp[num]++;
        ans = max(mp[num],ans);
    }
    cout << n - ans << endl;
    return 0;
}