用的线段树......

#include <stdio.h>
#include <memory.h>
const int maxn=50001;
struct node{
    int l,r,tot;
};
node a[maxn*2];    
int i,j,n,m,ans[maxn];
void maketree(int node,int l,int r)
{
    int mid;
    if (l>r) return;
    a[node].l=l;a[node].r=r;
    a[node].tot=r-l+1;
    mid=(l+r)/2;
    if (l==r) return;
    maketree(node*2,l,mid);
    maketree(node*2+1,mid+1,r);
}    
    
int max(int a1,int a2)
{
    if (a1>a2) return a1;
    return a2;
}    
int find(int now,int k)
{
    a[now].tot--;
    if (a[now].r==a[now].l)
        return a[now].l;
    else
    if (a[now*2].tot>=k)
        return find(now*2,k);
    else 
        return find(now*2+1,k-a[now*2].tot); 
}        
int main()
{
    while ((scanf("%d %d",&n,&m))!=EOF)
    {
        if (n==-1) return 0;
        memset (a,0,sizeof(a));
        for (i=1;i<=n;i++)
        {
            ans[i]=max(1,m-(n-i)*(n-i-1)/2+1);
            m-=ans[i]-1;
        }
        maketree(1,1,n);
        for (i=1;i<n;i++) printf("%d ",find(1,ans[i]));
        printf("%d\n",find(1,ans[n]));
    }
}        

• 我random了一堆数据，都没问题啊...... (11) TN 2005-05-27 15:29:53
  • smallest permutation 能保证么？ (13) frkstyc 2005-05-27 15:38:32
    • 能阿 (0) TN 2005-05-27 15:38:56
      • 这里就保证了吧？ (74) TN 2005-05-27 15:39:25
        • windbells写的数据试过了？他后面7-9开头的是错的 (78) frkstyc 2005-05-27 15:40:52
          • 什么意思？ (0) TN 2005-05-27 15:43:19
            • 他在discuss里面不是写了一堆数据么？ (0) frkstyc 2005-05-27 15:42:42
• Re:这个O(NLogN)的程序有什么错吗？奇怪了....... (22) dubiution 2007-04-03 00:01:19