三分算法

好久没总结算法了，希望能好好平衡吧~

三分的板子还是很重要的，不然边界情况会调得卡死人。。。

详细讲解：
https://www.acwing.com/file_system/file/content/whole/index/content/1631225/

补充例题：5201. 午餐音乐会

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

typedef long long LL;
const int N = 2e5 + 10;
int n;
int p[N], w[N], d[N];

LL check(int x){
    LL ans = 0;
    for(int i = 0; i < n; i++){
        if(p[i] < x){
            if(p[i] + d[i] < x){
                ans += (1LL*x - (p[i] + d[i])) * w[i];
            }
        }
        else{
            if(p[i] - d[i] > x){
                ans += (1LL* p[i] - d[i] - x) * w[i];
            }
        }
    }
    return ans;
}

void solve(){
    scanf("%d", &n);
    int l = 1e9 + 7, r = -1;
    for(int i = 0; i < n; i++) {
        scanf("%d%d%d", &p[i], &w[i], &d[i]);
        l = min(l, p[i]), r = max(r, p[i]);
    }
    //a>0的二次函数
    while(r - l > 1){
        int mid = l + r >> 1, mmid = mid + r >> 1;
        if(check(mid) > check(mmid)) l = mid;
        else r = mmid;
    }
    printf("%lld\n", min(check(l), check(r)));
}

int main(){
    solve();
    return 0;
}