P1338 末日的传说

· · 题解

P1338 末日的传说

题意

求长度为 n 的排列，满足条件：

思路

定义 f_i 表示在一个序列 a 中的第 i 项，满足 j>i 且 a_j<a_i 的所有可能的 j 的个数。
明显地，当 f 序列确定时，可以通过以下方法构造出答案序列 ans：

  1. 按 f_i 为第一关键字，i 为第二关键字进行排序。
  2. 排序后从小到大赋值 ans_i。
  3. 按原顺序（排序前顺序）输出。

那么应当如何构造出序列 f 呢？
可以发现 f 具有以下性质：

  1. 满足 $j>i$ 的 $j$ 只会有 $n-i$ 个。
  2. 要使序列 ans 的字典序最小，要尽可能使 f 末尾的值最大。

由此可得贪心策略：尽可能让 f_i 末尾的值在不超过 n-i 的情况下最大。详见代码。

代码

//08 24 1/1
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=5e4+5;
struct node{
    int val,id,num;
    bool operator<(const node &o)const{
        if(val==o.val){
            return id<o.id;
        }
        return val<o.val;
    }
}a[N];
bool cmp(node a,node b){
    return a.id<b.id;
}
int n,m;
signed main(){
//  freopen("legend.in","r",stdin);
//  freopen("legend.out","w",stdout);
    cin>>n>>m;
    for(int i=n;i>=1;i--){
        if(m==0){
            a[i].id=i;
//          cerr<<0<<" "<<m<<endl;
            continue;
        } 
        if(m<=n-i){
            a[i].val=m;
            a[i].id=i;
            m=0;
            continue;
        }
        a[i].val=n-i;
        a[i].id=i;
        m-=n-i;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        a[i].num=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        cout<<a[i].num<<" ";
    }
    return 0;
}