随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

PKU 2828 Buy Tickets

题目链接:http://poj.org/problem?id=2828

/*
题意:
    给定N(1 <= N <= 200000)个整数对(A,B),表示在A右边的位置插入一个B,
经过N次操作后问最后的B序列的排列情况。
题解:
    树状数组 或者 线段树

思路:
    这题的数据量比较大,一开始可以模拟一下过程,但是直接暴力肯定是超时
的,因为每次插入过程,这个位置的后面的元素必然是要顺序往后移动的。所以
总的复杂度高达O(n^2)。
    但是这个问题可以转化,我们这样考虑,对于任意两个整数对(A1,B1)和(A2,B2)
保证(A1,B1)在(A2,B2)之前出现,如果A1小于A2,后面的整数对是不影响前面整
数对的位置关系的,否则B1的位置必然要受到B2的影响而向后移动一位。
    于是A1和A2之间就存在一个逆序关系,我们可以联想到树状数组求逆序数时
候的做法,从后往前,对于最后一个数,它的位置就是An,因为之后没有插入数
了,它已经稳定下来了,然后将这个位置插入到树状数组的相应位置去,每次扫
描到当前数的时候二分枚举当前数前面有多少“空位”,空位的统计可以采用树
状数组的成段求和,找到后将这个数插入,N次操作后答案就保存下来了。
*/


#include 
<iostream>

using namespace std;

#define maxn 200010

int n;
int c[maxn];

struct point {
    
int A, B;
}
pt[maxn];

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


void add(int pos) {
    
while(pos <= n) {
        c[pos] 
++;
        pos 
+= lowbit(pos);
    }

}


int sum(int pos) {
    
int s = 0;
    
while(pos > 0{
        s 
+= c[pos];
        pos 
-= lowbit(pos);
    }

    
return s;
}


int ans[maxn];

int main() {
    
int i;
    
while(scanf("%d"&n) != EOF) {
        
for(i = 1; i <= n; i++)
            c[i] 
= 0;
        
for(i = 1; i <= n; i++{
            scanf(
"%d %d"&pt[i].A, &pt[i].B);
            pt[i].A 
++;
        }

        
for(i = n; i >= 1; i--{
            
int l = 1;
            
int r = n;
            
int as = 1;
            
while(l <= r) {
                
int m = (l + r) >> 1;
                
if(m - sum(m) >= pt[i].A) {
                    r 
= m - 1;
                    
as = m;
                }
else
                    l 
= m + 1;
            }

            ans[
as= pt[i].B;
            add(
as);
        }

        
for(i = 1; i <= n; i++{
            
if(i != 1)
                printf(
" ");
            printf(
"%d", ans[i]);
        }

        puts(
"");
    }

    
return 0;
}

posted on 2011-04-09 15:06 英雄哪里出来 阅读(1592) 评论(0)  编辑 收藏 引用 所属分类: 线段树树状数组


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理