富途9.18后端笔试

#include<iostream>
#include<map>
#include<math.h>
using namespace std;

const int N = 3e5 + 10;
int q[N];
map<int, int> m;
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> q[i];
    for(int i = 0; i < n; i ++) {
        m[q[i] + 1] ++;
        m[q[i] - 1] ++;
        m[q[i]] ++;
    }
    int a, b = 0;
    for(auto & t : m) {
        if(t.second > b) {
            a = t.first;
            b = t.second;
        }
    }
    int sum = 0;
    //cout << a << endl;
    for(int i = 0; i < n; i ++) {
        if(abs(a - q[i]) <= 1) sum ++;
    }
    cout << sum;
    return 0;
}

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int N = 1e5 + 10;
int q[N];
//二分查找
int query(int l, int r, int mx) {
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if(q[mid] <= mx) {
            l = mid;   
        } else {
            r = mid - 1;
        }
    }
    return l;
}
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> q[i];
    sort(q, q + n);
    int res = 0x3f3f3f3f;
    for(int i = 0; i < n; i ++) {
        int mx = q[i] + n - 1;
        //二分
        int j = query(i, n - 1, mx);
        int num = j - i + 1;
        res = min(res, n - num);
    }
    cout << res;
}