AtCoder Beginner Contest 143 D题（二分查找）

手写lower_bound()

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

const int N = 2e3 + 10;

int n;
int a[N];

int lower_search(int l, int r, int val) {
    while(l <= r) {
        int mid = l + r >> 1;
        if(a[mid] < val) l = mid + 1; //upper_bound 的话就是 a[mid] <= val
        else r = mid - 1;
    }
    return l;
} 

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            int pos = lower_search(1, n, a[i] + a[j]);
            ans += pos - j - 1;
        }
    }
    cout << ans << endl;

    return 0;
}