[JZOJ 3873]「提高A组模拟」『贪心』『构造』乐曲创作

题解 贪心 构造

题目描述

小可可是音乐学院的一名学生，他需要经常创作乐曲完成老师布置的作业。

可是，小可可是一个懒惰的学生。所以，每次完成作业时，他不会重新创作一首新的乐曲，而是去修改上一次创作过的乐曲作为作业交给老师。小可可的乐曲由N个音调不同的音符组成，分别记为音符1…N。因此，他创作的乐曲是由1…N的一个排列构成，例如N=5时，他创作的乐曲可能为：2,1,3,5,4。但是，小可可每一次会按照一定的要求修改上一次创作的乐曲。他规定，修改过后的乐曲必须与上一次创作的乐曲的悦耳值相同。所谓悦耳值就是他所创作的乐曲，也就是1…N的排列中逆序对的个数。逆序对是指对于1…N的一个排列A1,A2,...,An中的两个数Ai,Aj，满足iAj，例如：2,1,3,5,4 这个排列中有2个逆序对，分别为：(2,1)，(5,4)。可是，满足条件的排列有很多，小可可会选择在这些满足条件的排列中字典序大于上次创作乐曲的排列的字典序，且字典序尽量小的那一个排列作为新的乐曲。这里的字典序指：排列A：A1,A2…An和排列B：B1,B2…Bn，若存在一个数k，使得Ak

由于小可可最近要参加学校的篮球比赛，他没有空余时间完成老师布置的作业，于是他希望作为他好友的你帮助他完成作业。

1$\le$N$\le$5000000

题解

题目大意

有一长为$n$的序列$A$，现在需构造一新序列$B$，满足$A>B$且$A$的逆序对个数等于$B$的逆序对个数，求最小的$B$

思路

用树状数组求出第$i$个位置上贡献的逆序对个数$p_i$和总逆序对$sum_i$，显然有$sum_i=sum_{i+1}+p_i$

然后倒序枚举位置$i$，满足

• $p_i+1\le sum_i$
• $\frac{(n-i)(n-i-1)}{2}+p_i+1\ge sum_i$
• $a_i<\max\{a_{i+1}...a_n\}$

找到最大的$i$，并且将大于$a_i$中的最小的$a_j$与$a_i$交换位置（$\text{swap}(a_i,a_j)$）

然后将$i+1$到$n$升序排列，这使得从$i+1$到$n$不产生任何逆序对

然后找到要与$i+1$更换的数$pos$，这个数使得$pos+1$到$n$降序排列加上$pos$贡献的逆序对正好等于要求的逆序对

随后输出：

$1$到$i-1$不变，$i$与$j$交换，$i+1$到$pos$升序，$pos+1$到$n$降序

Code

#include<cstdio>
#include<algorithm>
#define N 500005
#define inf 123456789
#define ll long long
using namespace std;
ll n,pos,a[N],p[N],sum[N],mx[N],c[N];
bool cmp(int x,int y) {return x>y;}
int lowbit(int x) {return x&-x;}
int query(int x)
{
    ll res=0;
    for (ll i=x;i;i-=lowbit(i))
        res+=c[i];
     return res;
}
void update(ll x)
{
    for (ll i=x;i<=n;i+=lowbit(i))
        ++c[i];
}
void work(ll x,ll num)
{
    sort(a+x,a+n+1);
    for (ll i=x;i<n;++i)
    {
        ll res=(n-i)*(n-i-1)/2;
        if (res<num)
        {
            swap(a[i],a[i+num-res]);
            sort(a+i+1,a+n+1,cmp);
            for (ll i=1;i<=n;++i)
                printf("%lld ",a[i]);
            return; 
        }
    }
    for (ll i=1;i<=n;++i)
        printf("%lld ",a[i]);
}
int main()
{
    scanf("%lld",&n);
    for (ll i=1;i<=n;++i)
        scanf("%lld",&a[i]);
    for (ll i=n;i;--i)
    {
        p[i]=query(a[i]-1);
        sum[i]=sum[i+1]+p[i];
        mx[i]=max(mx[i+1],a[i]);
        update(a[i]);   
    } 
    a[n+1]=inf;
    for (ll i=n-1;i;--i)
    {
        if (((n-i)*(n-i-1)/2)+p[i]+1>=sum[i]&&p[i]+1<=sum[i]&&mx[i]>a[i])
        {
            pos=n+1;
            for (ll j=i+1;j<=n;++j)
                if (a[j]>a[i]&&a[j]<a[pos]) pos=j;
            swap(a[i],a[pos]);
            work(i+1,sum[i]-p[i]-1);
            return 0;
        }
    }
    return 0;
}