小小粉丝度度熊 二分答案 ＋ two pointer

http://acm.hdu.edu.cn/showproblem.php?pid=6119

发现自己的two pointer能力超弱。

这题是合并时间后，二分答案。

可以知道对于每个时间区间，合法的答案肯定是从其开始时间，向左扩展

或者从其结束时间，向右扩展。

复杂度O(2n log val)

细节有点恶心

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = 100000 + 20;
struct Node {
    int be, en;
    bool operator < (const struct Node & rhs) const {
        if (be != rhs.be) return be < rhs.be;
        else return en < rhs.en;
    }
}node[maxn];
int m, n;
LL sum[maxn];
bool check(LL val) {
    int p1 = 1, p2 = 1;
    while (p1 <= n) {
        while (p2 <= n && node[p2].en - node[p1].be + 1 < val) {
            p2++;
        }
        if (p2 == n + 1) {
            LL cut = sum[n] - sum[p1];
            cut += node[p1].be + val - 1 - node[n].en;
            if (cut <= m) return true;
            p1++;
            continue;
        }
//        if (node[p2].en - node[p1].be + 1 < val) break;
        if (node[p2].be - node[p1].be + 1 > val) {
            if (sum[p2 - 1] - sum[p1] + node[p1].be + val - 1 - node[p2 - 1].en <= m) return true;
        } else {
            if (sum[p2] - sum[p1] <= m) return true;
        }
        p1++;
    }
    p1 = p2 = 1;
    while (p2 <= n && node[p2].en < val) p2++;
    while (p2 <= n) {
        while (p1 <= n && node[p2].en - node[p1].en + 1 > val) {
            p1++;
        }
        if (node[p2].en - node[p1].be + 1 >= val) {
            if (sum[p2] - sum[p1] <= m) return true;
        } else {
            LL cut = sum[p2] - sum[p1];
            LL to = node[p2].en - val + 1;
            cut += node[p1].be - to;
            if (cut <= m) return true;
        }
        p2++;
    }
    return false;
}
void work() {
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &node[i].be, &node[i].en);
    }
    sort(node + 1, node + 1 + n);
    int len = 1;
    for (int i = 2; i <= n; ++i) {
        if (node[len].en >= node[i].be) node[len].en = max(node[len].en, node[i].en);
        else {
            node[++len] = node[i];
        }
    }
    n = len;
    for (int i = 2; i <= n; ++i) {
        sum[i] = sum[i - 1] + node[i].be - node[i - 1].en - 1;
    }
    LL be = 0, en = 1e15;
    for (int i = 1; i <= n; ++i) {
        be = max(be, 1LL * node[i].en - node[i].be + 1);
    }
    while (be <= en) {
        LL mid = (be + en) >> 1;
        if (check(mid)) be = mid + 1;
        else en = mid - 1;
    }
    cout << en << endl;
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    while (scanf("%d%d", &n, &m) > 0) work();
    return 0;
}