首页 > 代码库 > UVA_11525 树状数组的活用 二分

UVA_11525 树状数组的活用 二分

2024-07-12 04:04:10   221人阅读

我们知道1——k有K！种排列，现在给定k和n，要你按字典序输出 第n种排列的数列

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

k最大为50000，直接算出来不可能，我发现这个n的表达式很有意思，明显（k-1）！就是表示第一次除第一个以外，剩下k-1个数的排列个数，乘一个S1就说明之前用了多少次这种排列了，根据这个 再手算了一下，发现就是，每次找第Sk个数，输出，当然已经访问过的数就要T出去

这很明显就是树状数组 （或者线段树的单点修改和查询）功能，先初始化每个都是大小为1，然后每次二分找第Sk个，找到之后，把该位置置为-1，消除该位的影响，继续找，继续输出即可。你看题目里给定的S的范围也就是顺应这个，故意把剩下几个数，S就恰好限定在这个里面

发现自己二分写的还不是很熟，一开始还搞了一下子，是用mid还是L做结果呢 最后在我的写法里被证明是用L做结果

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define N 50000+10using namespace std;int A[N];int n;int lowbit(int x){    return x&(-x);}void add(int x,int v){    while (x<=n){        A[x]+=v;        x+=lowbit(x);    }}void init(){    for (int i=1;i<=n;i++){        add(i,1);    }}int query(int x){    int ret=0;    while (x>0){        ret+=A[x];        x-=lowbit(x);    }    return ret;}int main(){    int t;    scanf("%d",&t);    while (t--)    {      scanf("%d",&n);      init();      for (int i=1;i<=n;i++){        int a;        scanf("%d",&a);        int L=1,R=n,mid;        while (L<R)        {            mid=(L+R)>>1;            int tmp=query(mid);            //if (tmp==a+1) break;            if (tmp<a+1) L=mid+1;            else R=mid;        }        //cout<<"@@"<<mid<<endl;        add(L,-1);        printf("%d",L);        if (i<n) putchar(‘ ‘);      }      puts("");    }    return 0;}

 


联系
我们