题解：P2107 小Z的AK计划

· · 题解

为什么题解只有堆和排序，这明明也是一道线段树二分的好题。

思路

首先显然的思路就是一个 DP。先将每个机房按照 x_i 排序，dp_i 表示最远走到第 i 个机房时最多在几个机房 AK。这里我们可以把走到第 i 个机房与 AK 一个机房这两件事分开。可得当走到第 i 个机房时，小 Z 用来 AK 的时间为 m-x_i。

随后可以看出，我们就会想要在 [1,i] 的区间内不断去 AK 需要时间最少的机房，直到时间不够用为止。而这个功能用一个线段树可以轻松实现，具体是这样的：

最后在每一次查询后取一个最大值即可。时间复杂度 O(n\log n)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll (k<<1)
#define rr (k<<1|1)
#define mid ((l+r)>>1)
struct node {
    int x, t, id;
} a[6000005];
bool cmp(node x, node y) {
    return x.x < y.x;
}
bool cmp2(node x, node y) {
    return x.t < y.t;
}
int n, m;
struct tree {
    int l, r, num, sum;
} t[10000005];//sum表示要把这个区间内的所有机房全部 AK 所需的时间，num 表示这个区间内机房的数量
void build(int k, int l, int r) {
    t[k].l = l;
    t[k].r = r;
    if (l == r) return ;
    build(ll, l, mid);
    build(rr, mid + 1, r);
    return ;
}
void pushup(int k) {
    t[k].num = t[ll].num + t[rr].num;
    t[k].sum = t[ll].sum + t[rr].sum;
    return ;
}
void update(int k, int c, int p) {
    if (t[k].l > c || t[k].r < c) return ;
    if (t[k].l == t[k].r) {
        t[k].num = 1;
        t[k].sum = p;
        return ;
    }
    update(ll, c, p);
    update(rr, c, p);
    pushup(k);
}
int query(int k, int num) {
    if (t[k].l == t[k].r) return (num >= t[k].sum) ? t[k].num : 0;
    if (t[k].sum <= num) return t[k].num;
    if (t[ll].sum <= num) return t[ll].num + query(rr, num - t[ll].sum);
    return query(ll, num);
}//线段树二分，不能理解可以多看看
int ans;
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].t;
    sort(a + 1, a + n + 1, cmp2);
    for (int i = 1; i <= n; i++) a[i].id = i;
    sort(a + 1, a + n + 1, cmp);
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        m -= a[i].x - a[i - 1].x;
        update(1, a[i].id, a[i].t);
        ans = max(ans, query(1, m));
    }
    cout << ans;
    return 0;
}