ZOJ2425

题意很简单，就是给出n,m求n个数下逆序个数为m的最小排列，求出最小排列。
我用的暴力+贪心的方法。  用m与当前个数（也就是剩下需要写出的个数）的最大逆序个数进行比较，容易知道当前逆序最大的个数为s=(n)*(n-1)/2;
如果s==m直接逆序打印没用过的数。如果m<s,那么继续用m与s1=（n-1）(n-2)/2,(n-1个最大逆序个数比较)，然后找出没用过的（m-s1+1）个数，即为当前要打印的个数，
如果 m>=s,直接找一个最小没用过的数打印。

一开始没用long long还有各种细节不注意错了好几次，代码写得也很烂，网上好像有其他更简单的方法。

下面是AC代码：
[cpp] 
#include<iostream> 
#include<cstdio> 
using namespace std; 
int mark[50005]; 
 
int main(){ 
 
    int i,j; 
 
    long long n,m,t; 
 
    while(cin>>n>>m){ 
      // printf("%I64d/n",m); 
        if(n==-1&&m==-1) 
            break; 
        long long s=n*(n-1)/2; 
    //  cout<<s<<endl; 
    //  printf("%I64d/n",s); 
    //  return 0; 
        int flag=1; 
        t=n; 
        for(i=1;i<=n;i++) 
            mark[i]=0; 
 
        if(m==0){ 
            cout<<1; 
            for(i=2;i<=n;i++) 
                cout<<" "<<i; 
            cout<<endl; 
 
        } 
        else{ 
 
 
            while(m){ 
                if(m==s){ 
                    for(i=n;i>=1;i--){ 
 
                        if(mark[i]==0){ 
                            if(flag){ 
                                flag=0; 
                                cout<<i; 
                                mark[i]=1; 
 
                            } 
                            else{ 
                                cout<<" "<<i; 
                                mark[i]=1; 
                            } 
                        } 
                    } 
                    break; 
 
                } 
                else if(m<s){ 
                    long long nexts=(t-1)*(t-2)/2; 
                    if(m>nexts){ 
                        long long key=m-nexts; 
                        int count=0,k; 
 
                        for(i=1;i<=n;i++){ 
                            if(count==key+1) break; 
                            if(mark[i]==0){ 
                                count++; 
                                k=i; 
                            } 
                        } 
                        if(flag){ 
                            cout<<k; 
                            flag=0; 
 
                        } 
                        else{ 
                            cout<<" "<<k; 
                        } 
                        mark[k]=1; 
 
                        m=nexts; 
                    } 
                    else{ 
                        for(i=1;i<=n;i++) 
                            if(mark[i]==0){ 
                                if(flag){ 
                                    flag=0; 
                                    cout<<i; 
                                    mark[i]=1; 
                                    break; 
                                } 
                                else{ 
                                    cout<<" "<<i; 
                                    mark[i]=1; 
                                    break; 
                                } 
                            } 
 
                    } 
                } 
                t--; 
                s=t*(t-1)/2; 
            } 
            cout<<endl; 
        } 
    } 
 
 
 
    return 0; 
}