一道二分题,73分求助!!!多谢!
  • 板块P1102 A-B 数对
  • 楼主LukeSu
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/4/2 14:43
  • 上次更新2023/10/28 04:52:04
查看原帖
一道二分题,73分求助!!!多谢!
593753
LukeSu楼主2022/4/2 14:43
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 222222;
int a[maxn];

signed main(){
    cin.tie(0)->sync_with_stdio(false);
    int N, C, ans1 = 0, ans2 = 0, res = 0;
    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 l = i + 1, r = N;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(a[mid] <= a[i] + C) l = mid;
            else r = mid - 1;
        }
        ans1 = r;
        l = i, r = N; 
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(a[mid] < a[i] + C) l = mid;
            else r = mid - 1;
        }
        ans2 = r;
        res += (ans1 - ans2);
    }
    cout << res;

    return 0;
}
2022/4/2 14:43
加载中...