http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=4791

（1）第一次寫浙大的題目，這題讓我十分意外，基本的線段樹類型（求第x個空位）。

（2）電影院里，一次插入一個人，讓他坐在第x個空位shang?（每個x均給定)。求最終的位置安排（制定一些人，求他們各自的座號）。

具體代碼：

View Code #include<stdio.h> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 const int maxn=51000; int n, m; int pos[maxn], sum[maxn<<2]; void pushup(int rt) {sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l, int r, int rt) {sum[rt]=r-l+1;if(l==r){return ;}int m=l+r>>1;build(lson);build(rson); } void insert(int p, int i, int l, int r, int rt) {if(l==r){sum[rt]=0;pos[i]=l;return ;}int m=l+r>>1;if(p<=sum[rt<<1]) insert(p, i, lson);else insert(p-sum[rt<<1], i, rson);pushup(rt); } int main() {while(scanf("%d", &n)!=EOF){build(1, n, 1);for(int i=1;i<=n;i++){int p;scanf("%d", &p);insert(p, i, 1, n, 1);}scanf("%d", &m);for(int i=1;i<=m;i++){int x;scanf("%d", &x);if(i!=1) printf(" %d", pos[x]);else printf("%d", pos[x]);}printf("\n");}return 0; }

?

轉載于:https://www.cnblogs.com/tim11/archive/2012/08/26/2657392.html

總結

以上是生活随笔為你收集整理的浙大月赛C题（2012/8）Cinema in Akiba（线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。