P1338 末日的传说（贪心）

P1338

题意就是求逆序对个数为m的字典序最小的序列

   这题就是贪心安排每个位置的数，对于位置i，要放什么数取决于m和剩余的n-i个数能组成的逆序最大数(n-i)*(n-i-1)/2有关,①若是小于，则说明i位置可以放当前最小的数，能放最小的数肯定要放，因为要字典序最小,②若是大于，如果还是按当前最小的放到i位置，那么剩下的数就肯定不能构造出m个逆序对了，那么放在i位置的数就得是剩下的数里第m-(n-i)*(n-i-1)/2+1个数了，这样才能因为这样放的话，必定有m-(n-i)*(n-i-1)/2个比它小的数放在了i+1位置以后了.
vector.erase() 参数写地址 v.begin()+a可以得到v里v[a]的地址

#include<bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs (rt<<1)+1
#define PI acos(-1)
#define eps 1e-8
#define ll long long
#define fuck(x) cout<<#x<<"     "<<x<<endl;
typedef pair<int,int> pii;
const int inf=2e9;
const int maxn=1e6+10;
int d[4][2]={1,0,-1,0,0,1,0,-1};
//int lowbit(int x){return x&-x;}
//void add(int x,int v){while(x<=n)bit[x]+=v,x+=lowbit(x);}
//int sum(int x){int ans=0;while(x>=1) ans+=bit[x],x-=lowbit(x);return ans;}
inline ll read() {
    ll s = 0,w = 1;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') w = -1;
        ch = getchar();
    }
    while(isdigit(ch))
        s = s * 10 + ch - '0',ch = getchar();
    return s * w;
}
inline void write(ll x) {
    if(x < 0)
        putchar('-'), x = -x;
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
int pos[maxn];
vector<int>v;
ll n,m;

int main(){
    n=read();
    m=read();
    for(int i=1;i<=n;i++){
        v.push_back(i);
    }
    for(int i=1;i<=n;i++){
       // fuck(i);
        if(m<=(n-i)*(n-i-1)/2)
        {
            pos[i]=v[0];
            v.erase(v.begin());
        }
        else
        {
            pos[i]=*(v.begin()+m-(n-i)*(n-i-1)/2);
            v.erase(v.begin()+m-(n-i)*(n-i-1)/2);
            m=(n-i)*(n-i-1)/2;
        }

    }
    for(int i=1;i<=n;i++)
        write(pos[i]),printf(" ");
    puts("");
    return 0;
}