Buy Tickets

There will be several test cases in the input. Each test case consists of N + 1 lines where N $(1 \leq N \leq 200,000)$ is given in the first line of the test case. The next N lines contain the pairs of values Posi and Vali in the increasing order of i $(1 \leq i \leq N)$ . For each i, the ranges and meanings of $Pos_i$ and $Val_i$ are as follows:

$Pos_i \in [0, i − 1]$ — The i-th person came to the queue and stood right behind the $Pos_i-th$ person in the queue. The booking office was considered the 0th person and the person at the front of the queue was considered the first person in the queue.
Vali ∈ [0, 32767] — The i-th person was assigned the value $Val_i$ .
There no blank lines between test cases. Proceed to the end of input.

C++14(g++5.4) 解法, 执行用时: 181ms, 内存消耗: 4580K, 提交时间: 2020-08-10 16:28:57

//Author:XuHt
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 200006;
int n, ans[N], p[N], v[N], c[N];

int ask(int x) {
	int ans = 0;
	while (x) {
		ans += c[x];
		x -= x & -x;
	}
	return ans;
}

void add(int x, int y) {
	while (x <= n) {
		c[x] += y;
		x += x & -x;
	}
}

int get(int x) {
	int l = 1, r = n;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (ask(mid) < x) l = mid + 1;
		else r = mid -1;
	}
	return l;
}

void Buy_Tickets() {
	memset(c, 0, sizeof(c));
	for (int i = 1; i <= n; i++) add(i, 1);
	for (int i = 0; i < n; i++) scanf("%d %d", &p[i], &v[i]);
	for (int i = n - 1; i >= 0; i--) {
		int t = get(p[i] + 1);
		ans[t] = v[i];
		add(t, -1);
	}
	for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
	puts("");
}

int main() {
	while (cin >> n) Buy_Tickets();
	return 0;
}

C++ 解法, 执行用时: 785ms, 内存消耗: 2412K, 提交时间: 2022-02-16 15:25:43

#include<string>
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
/*====================*/
int main()
{
	int n; while (cin >> n)
	{
		vector<int>line;
		for (int i = 1; i <= n; ++i)
		{
			int pos, id; 
			cin >> pos >> id;
			line.insert(line.begin() + pos, id);
		}
		for (auto x : line)
		{
			cout << x << " ";
		}
		cout << endl;
	}
	return 0;
}

详情