ZOJ Monthly, August 2012 - C : Cinema in Akiba
問題概要
1~N(N<10^5)の座席があり、最初は全部空である。i人目の客は左からa[i]番目の空席に座る。各人がどの座席に座ったか求める問題。
解法
BITを使う典型問題。
acceptされたコード
#include <cstdio> #include <vector> using namespace std; BinaryIndexedTree bitree; const int MAX_N = 50000; const int MAX_Q = 3000; int N, Q; int Qs[MAX_Q], as[MAX_N], ans[MAX_N]; bool init() { if (scanf("%d", &N) == EOF) { return false; } for (int i = 0; i < N; ++i) { scanf("%d", as + i); } scanf("%d", &Q); for (int i = 0; i < Q; ++i) { scanf("%d", Qs + i); --Qs[i]; } return true; } void solve() { bitree.init(N); for (int i = 0; i < N; ++i) { bitree.add(i, 1); } for (int i = 0; i < N; ++i) { ans[i] = bitree.getOverSumIndex(as[i] - 1); bitree.add(ans[i], -1); } for (int i = 0; i < Q; ++i) { printf("%d%c", ans[Qs[i]] + 1, i == Q-1 ? '\n': ' '); } } int main() { for (;init();) { solve(); } return 0; }