求助,为什么TLE啊
查看原帖
求助,为什么TLE啊
530570
Firrel_qaq楼主2022/5/14 10:38
#include <bits/stdc++.h>
int a[200010], n, c;
long long ans = 0;
using namespace std;
int first_found(int k){
    int l = 1, r = n, nans = -1;
    while(l <= r){
        int mid = (r + l) / 2;
        if(a[mid] == k){
            nans = mid;
            r = mid + 1;
        }
        else if(a[mid] < k){
            l = mid - 1;
        }
        else{
            r = mid + 1;
        }
    }
    return nans;
}
int last_found(int k){
    int l = 1, r = n, nans = -1;
    while(l <= r){
        int mid = (r + l) / 2;
        if(a[mid] == k){
            nans = mid;
            l = mid - 1;
        }
        else if(a[mid] < k){
            l = mid - 1;
        }
        else{
            r = mid + 1;
        }
    }
    return nans;
}
int main() {
    cin >> n >> c;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) {
        int y = first_found(a[i] + c);
        int x = last_found(a[i] - c);
        if(x == -1) continue;
        ans += y - x + 1; 
    }
    cout << ans;
    return 0;
}
2022/5/14 10:38
加载中...