题解：P2107 小Z的AK计划

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

思路

首先显然的思路就是一个 DP。先将每个机房按照

x_i

排序，

dp_i

表示最远走到第

i

个机房时最多在几个机房 AK。这里我们可以把走到第

i

个机房与 AK 一个机房这两件事分开。可得当走到第

i

个机房时，小 Z 用来 AK 的时间为

m-x_i

。

随后可以看出，我们就会想要在

[1,i]

的区间内不断去 AK 需要时间最少的机房，直到时间不够用为止。而这个功能用一个线段树可以轻松实现，具体是这样的：

最开始先将每个机房按照 $t_i$ 排序，并将排序后的第 $i$ 个机房的位置定义为其在线段树上的位置，记录为 $id_i$ ；
接着再将每个机房按照 $x_i$ 排序，之后依次访问每个机房。当访问到第 $i$ 个机房时，先在线段树上 $id_i$ 的位置插入权值为 $t_i$ 的点，随后查询当最大时间为 $m-x_i$ 时最多可以 AK 的机房数量。实现上就是一个裸的线段树二分。

最后在每一次查询后取一个最大值即可。时间复杂度

O(n\log n)

。

代码

CPP

#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;
}

题解：P2107 小Z的AK计划

文章操作

思路

代码

相关推荐

评论

题解：P2107 小Z的AK计划