求助:桶排序跳跃 85pts
查看原帖
求助:桶排序跳跃 85pts
1434247
Prefixium楼主2024/11/1 19:20
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int b[N], a[N];
int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[a[i]]++;
    }
    
    int idx = 0;
    for (int i = 1; i <= N; i++) {
        int t = b[i];
        while(t--) a[++idx] = i;
    }    
    
    int cnt = 0;
    for (int i = 1; i + b[a[i]] <= n; i++) {
        if (a[i] < a[i + b[a[i]]]) cnt++;
    }
    cout << n - cnt;
    return 0;
} 
2024/11/1 19:20
加载中...