# 官方题解｜欢乐赛#42 T6

T6

思路分析

本题考查贪心，数据范围很小，可以采用 $O(n^2)$ 的时间复杂度。我们可以先把所有的元素排个序，然后依次从前往后选，如果满足当前选的比前一个选的大就选上，并统计答案，记得把选过的标记一下，一直选到不能选为止即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int a[N], n;
bool st[N];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    bool f = 0;//f等于0的时候，表示一个还没选，等于1表示前面已经有选的了
    int x, sum = 0;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            if(st[j] == 0){
                if(f == 0) {//等于0的时候代表现在要选第一个，所以不产生贡献
                    x = a[j], f = 1;
                    st[j] = 1;
                }
                else if(a[j] > x){
                    x = a[j];
                    sum ++;
                    st[j] = 1;
                }
            }
            if(j == n) f = 0;
        }
    }
    cout << sum;
    return 0;
}