首页 > 代码库 > POJ 2828 Buy Tickets
POJ 2828 Buy Tickets
从后往前每个找出前面恰好留出k个位置 的位置就可以。
//============================================================================// Name : F.cpp// Author : L_Ecry// Version :// Copyright : Your copyright notice// Description : Hello World in C++, Ansi-style//============================================================================#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#define N 200050using namespace std;int sum[N * 4];void build(int l, int r, int i) { sum[i] = r - l + 1; if (l != r) { int mid = (l + r) >> 1; build(l, mid, i << 1); build(mid + 1, r, i << 1 | 1); }}int update(int l, int r, int va, int i) { sum[i]--; if (l == r) { return l; } int mid = (l + r) >> 1; if (sum[i << 1] > va) return update(l, mid, va, (i << 1)); else return update(mid + 1, r, va - sum[i << 1], (i << 1 | 1));}int n;int ans[N];int x[N], y[N];int main() { while (scanf("%d", &n) != EOF) { build(1, n, 1); for (int i = 0; i < n; ++i) scanf("%d%d", &x[i], &y[i]); for (int i = n-1; i >-1; --i) { int tmp = update(1, n, x[i], 1); ans[tmp] = y[i]; } for (int i = 1; i < n; ++i) { printf("%d ", ans[i]); } printf("%d\n",ans[n]); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。