[数据结构与算法]AcWing120 防线

知识点：二分

这道题怎么说呢，不算难，感觉就是为了二分而二分，但是做这道题把原来理解错的东西发现了，以前一直以为二分的时候，如果有解的范围是1到n，那么最小化的时候，无解应该是n+1，我理解传1和n进去，那么无解就会最后变成n+1，其实不是这样的，如果你想要二分不仅要求解还要判断有没有解，那么你要自己把越界下标或者数据给加进去的，最后算出来是那个数那么就是无解

#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pa;

const int N = 2e5 + 5;
const ll Max = 0x7fffffff;

struct state {
    int s, e, d;
} st[N];

int n;

bool check(ll x) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (st[i].s > x) continue;
        if (st[i].e <= x) cnt += (st[i].e - st[i].s) / st[i].d + 1;
        else cnt += (x - st[i].s) / st[i].d + 1;
    }
    return cnt % 2;
}

void solve(ll l, ll r) {
    ll t = r;
    while (l < r) {
        ll mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    if (l == t) cout << "There's no weakness." << endl;
    else {
        cout << l << " ";
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (st[i].s > l || st[i].e < l) continue;
            if ((l - st[i].s) % st[i].d == 0) ans++;
        }
        cout << ans << endl;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> st[i].s >> st[i].e >> st[i].d;
        }
        solve(0, Max + 1);
    }
    return 0;
}