Codeforces Round #497 (Div. 2) ---- C Reorder the Array
程序员文章站
2022-06-04 08:28:16
...
给我们一些数字,我们把这个数字重新排列,那么会有一些位置的数大于这个位置上原来的数字,寻找这样的位置最多有多少。
有一种做法就是排序-贪心,最大的数优先放在比他小的最大的数字上
这里有一种方法,统计最大的出现过的数的次数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;
}
推荐阅读
-
Codeforces Round #649 (Div. 2) C-Ehab and Prefix MEXs
-
Codeforces Round #432 (Div. 2) - C - Five Dimensional Points
-
Codeforces Round #658 (Div. 2)C1. Prefix Flip (Easy Version)(贪心)
-
Codeforces Round #658 (Div. 2) (C1、C2)
-
Codeforces Round #320 (Div. 2) C. A Problem about Polyline ( 数学 )
-
Codeforces Round #659 (Div. 2) C、String Transformation 1(思维+set)
-
Codeforces Round #654 (Div. 2)-C. A Cookie for You
-
Educational Codeforces Round 85 (Rated for Div. 2) C. Circle of Monsters(前缀和 预处理 贪心)
-
Codeforces Round #651 (Div. 2) C. Number Game
-
Codeforces Round #643 (Div. 2) D. Game With Array