设为首页 加入收藏

TOP

uva 11525排列（树状数组 + 二分）
2015-11-21 01:01:37 来源: 作者: 【大 中 小】 浏览:2次
Tags：uva 11525 排列 +二分
?? 现在给定k和n，要你按字典序输出 第n种排列的数列

而且题目给的 n是 n=S1（k-1）！+S2(k-2)!+...+Sk-1*1!+Sk*0!(0=

我们可以知道si表示i后面有多少个比a[i]小的数，这样一来首先想到的就是set，但是set不能顺序访问，所以可以用树状数组，初始时置1，消除后置0，然后二分来求和为si + 1的位置

代码如下：

?

#include
  
     
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
              #include
              
                using namespace std; #define LL long long const int maxn = 50005; const int INF = 1000000000; //freopen("input.txt", "r", stdin); int c[2 * maxn], s[maxn], ans[maxn], k; int lowbit(int x) { return x&(-x); } int sum(int x) { int ret = 0; while(x > 0) { ret += c[x]; x -= lowbit(x); } return ret; } void add(int x) { while(x <= k) { c[x] += 1; x += lowbit(x); } } void subtract(int x) { while(x <= k) { c[x] -= 1; x += lowbit(x); } } int main() { int t; scanf("%d", &t); while(t--) { memset(c, 0, sizeof(c)); cin >> k; for(int i = 1; i <= k; i++) add(i); for(int i = 1; i <= k; i++) { int tmp; cin >> tmp; int le = 1, ri = k; while(le < ri) { int mi = (le + ri) >> 1; int tsum = sum(mi); if(sum(mi) >= tmp + 1) ri = mi; else le = mi + 1; } ans[i] = ri; subtract(ans[i]); } printf("%d", ans[1]); for(int i = 2; i <= k; i++) printf(" %d", ans[i]); printf("\n"); } return 0; }

?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：C++――2828: 素数判断 下一篇：BZOJ 1140 POI2009 KOD 编码 DFS

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: