首页 > 其他 > 详细

BestCoder Round #65 (ZYB's Premutation)

时间:2015-12-05 22:34:54      阅读:381      评论:0      收藏:0      [点我收藏+]

ZYB‘s Premutation

Accepts: 220
Submissions: 983
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 131072/131072 K (Java/Others)
问题描述
ZYBZYBZYB有一个排列PPP,但他只记得PPP中每个前缀区间的逆序对数,现在他要求你还原这个排列.

(i,j)(i<j)(i,j)(i < j)(i,j)(i<j)被称为一对逆序对当且仅当Ai>AjA_i>A_jA?i??>A?j??
输入描述
第一行一个整数TTT表示数据组数。

接下来每组数据:

第一行一个正整数NNN,描述排列的长度.

第二行NNN个正整数AiA_iA?i??,描述前缀区间[1,i][1,i][1,i]的逆序对数.

数据保证合法.

1≤T≤51 \leq T \leq 51T5,1≤N≤500001 \leq N \leq 500001N50000
输出描述
TTT行每行NNN个整数表示答案的排列.
输入样例
1
3
0 1 2
输出样例
3 1 2

心得:爆炸;BOOMBOOMBOOM;runtime errer了6次!!!!
只好瞄眼隔壁的了;树状数组+二分
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 50010 ;
int tree[maxn] ;
int n ;
int getsum(int x){
    int sum = 0 ;
    while(x){
       sum += tree[x] ;
       x -= x&(-x) ;
    }
    return sum ;
}
void update(int x , int dx){
    while(x <= n){
        tree[x] += dx ;
        x += x&(-x) ;
    }
}
int find(int x , int ss){
    int l = 1 ;
    int r = n ;
    while(l <= r){
        int mid = (l + r) >> 1;
        int sum = ss-(mid-getsum(mid)) ;
        if(sum > x){
           l=mid+1;
        }
        else if(sum <= x){
            r=mid-1 ;
        }
    }
    return r+1 ;
}
int a[maxn] ;
int ans[maxn] ;
int main()
{
   int t ;
   scanf("%d" , &t) ;
   while(t--){
       scanf("%d" , &n) ;
       for(int i = 1;i <= n;i++){
          scanf("%d" , &a[i]) ;
          tree[i] = 0 ;
       }
       for(int i = n;i >= 1;i--){
           int sum = a[i] - a[i-1] ;
           ans[i] = find(sum , i) ;
           update(ans[i] , 1) ;
       }
       for(int i = 1;i <= n;i++){
           printf("%d%c" , ans[i] , i == n ?\n: ) ;
       }
   }
   return  0;
}

 

BestCoder Round #65 (ZYB's Premutation)

原文:http://www.cnblogs.com/yoyo-sincerely/p/5022413.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!