题解：P10688 Buy Tickets

转化利用树状数组！！！

由于是排队问题，所以后进入队列的人拥有站在哪里的决定权，因此我们倒序处理进入队列的人。

因此每个人进入队列的时候，如果他的理想位置是

x

的话,他显然没有任意挑选位置的自主权，必须在剩下的位置里面挑选一个最满意的。

由此可知我们整道题所要做的就是维护一个数组，来存储第

k

个点以前剩余的座位个数，比如

find(5)=4

，就说明前五个座位里面还剩下四个，那么如果此时进入队列的人想坐在第四个位置，就要看

find(4)

是不是等于

4

，如果是，就要坐在第四个位置；否则，说明第五个位置没人坐，就坐在第五个位置。这也就是二分的思想。

CPP

int l = 1, r = n;
while (l < r) {
	int mid = (l + r) / 2;
	int t = find(mid);
	if (t < p[i]) {
		l = mid + 1;
	}
	else {
		r = mid;
	}
}

显然

find(i)

有前缀和的思想，而又要进行单点修改，所以就要借助树状数组。

CPP

inline int lowbit(int x) {
	return x & -x;
}

inline void add(int v, int x) {//单点修改
	for (int i = x; i <= n; i += lowbit(i)) {
		a[i] += v;
	}
}

inline int find(int x) {//求前缀和
	int ans = 0;
	for (int i = x; i > 0; i -= lowbit(i)) {
		ans += a[i];
	}
	return ans;
}

因此在第

i

座位被占用以后，使用

add(-1,i)

这个操作就行了，这样就很高效的完成树状数组的维护。

完整代码

CPP

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N = 200005;

int a[N], num[N], c[N], p[N];
int cnt, n;

inline int lowbit(int x) {
	return x & -x;
}

inline void add(int v, int x) {
	for (int i = x; i <= n; i += lowbit(i)) {
		a[i] += v;
	}
}

inline int find(int x) {
	int ans = 0;
	for (int i = x; i > 0; i -= lowbit(i)) {
		ans += a[i];
	}
	return ans;
}

int main(void) {
	while (cin >> n) {

		memset(a, 0, sizeof a);
		memset(c, 0, sizeof c);

		for (int i = 1; i <= n; i++) {
			cin >> p[i] >> num[i];
			p[i]++;
			add(1, i);
		}

		for (int i = n; i >= 1; i--) {
			int l = 1, r = n;
			while (l < r) {
				int mid = (l + r) / 2;
				int t = find(mid);
				if (t < p[i]) {
					l = mid + 1;
				}
				else {
					r = mid;
				}
			}
			c[r] = num[i];
			add(-1, r);
		}

		for (int i = 1; i <= n; i++) {
			cout << c[i] << ' ';
		}
		cout << endl;
	}
	return 0;
}

题解：P10688 Buy Tickets

文章操作

转化利用树状数组！！！

完整代码

相关推荐

评论

题解：P10688 Buy Tickets