题解：P12386 [蓝桥杯 2023 省 Python B] 混乱的数组

· · 题解

[蓝桥杯 2023 省 Python B] 混乱的数组

题目传送门

Solution

看到本题，先来一发打表。 毕竟是构造题，必须要找找规律。

4:  2 2 1 1 
5:  3 2 1 1
6:  4 3 2 1 

7:  2 3 2 1 1
8:  3 2 2 1 1
9:  4 3 2 1 1
10:  5 4 3 2 1

11:  2 4 3 2 1 1
12:  3 3 2 2 1 1 
13:  4 3 2 2 1 1
14:  5 4 3 2 1 1
15:  6 5 4 3 2 1

16:  2 5 4 3 2 1 1
17:  3 4 3 2 2 1 1
18:  4 3 3 2 2 1 1 
19:  5 4 3 2 2 1 1
20:  6 5 4 3 2 1 1
21:  7 6 5 4 3 2 1

22:  2 6 5 4 3 2 1 1 
23:  3 5 4 3 2 2 1 1 
24:  4 4 3 3 2 2 1 1
25:  5 4 3 3 2 2 1 1
26:  6 5 4 3 2 2 1 1
27:  7 6 5 4 3 2 1 1
28:  8 7 6 5 4 3 2 1

然后惊人地发现竟然对于所有最优解为 n 位的数，对应的答案相同位数的个数竟然都为 n-1 个，并且 n 位可构成逆序对数最多为 x=\dfrac{n(n-1)}{2}。

证明一下，当每一位都与其前面的全部位数构成逆序对时，其逆序对数 x 可表示为如下式子。

x=\sum_{i = 1}^{n-1} i=\dfrac{n(n-1)}{2}

那么贪心地，则可以找出可以拼出最多的逆序对的 n 使这个最多逆序对数刚好不小于 x。

long long n=1;
while(n*n-n<2*x) n++;

那么这个临界值可以特判输出，它们刚好是一个递减等差数列，首项为 n。

if((n*n-n)/2==x){
    cout<<n<<"\n";
    for(int i=n;i>=1;i--) 
        cout<<i<<" ";
}

然后再仔细观察可以发现，对于每组答案数列来说，有一部分里的数从第一个开始单调递减，有一部分，从第二个数开始单调递减。

第一种情况。

此部分的 x 的范围为 \dfrac{n(n-1)}{2}-\dfrac{(n+1)}{2}<x\leq \dfrac{n(n-1)}{2}。

因为，每次将第 i 个数以前的数全部减 1 就刚好使组成的逆序对减 1。所以直接将后面的一直减直至组成的逆序对数为 x 时停止。特别地，当一个数出现超过两次时，它每多出现一次就会让前方需要多加一点，使整体的字典序变大，所以要保证一个数最多出现两次。再以此贪心即可。

第二种情况。

此部分的 x 的范围为 \dfrac{(n-1)(n-2)}{2}<x\leq \dfrac{n(n-1)}{2}-\dfrac{(n+1)}{2}。

和上一种一样，只是将 \dfrac{n}{2}-(\dfrac{n(n-1)}{2}-\dfrac{(n+1)}{2}-x) 放在数列开头即可，后面做与前一种一样的操作。

简单证明一下。因为在临界情况 x=\dfrac{n(n-1)}{2}-\dfrac{(n+1)}{2} 时，已经是该长度整个数列全是单调递减的数的情况下字典序较小时可以表示的最小的答案了，再按方案一那样做会使字典序变大，所以要进行调整。所以我们在不浪费任意一个数所带来的贡献的情况下，加一个较小的数使前两位成为一个逆序对，再在后面进行简单调整，就可以实现在不影响字典序的情况下，将逆序对减少。非常容易证明，当取来放在开头的数为 \dfrac{n}{2}-(\dfrac{n(n-1)}{2}-\dfrac{(n+1)}{2}-x) 时刚好可以使逆序对数为答案所求。调整部分与情况一一样。

最终代码如下。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long x,a[N];
int main(){
    cin>>x;
    long long n=1;
    while(n*n-n<2*x) n++;
    if((n*n-n)/2==x){
        cout<<n<<"\n";
        for(int i=n;i>=1;i--) 
            cout<<i<<" ";
    }
    else {
        cout<<n<<"\n";
      //n为数列长度
        int p=(n+1)/2,d=(n*n-n)/2,tp=0;
        for(int i=1;i<=n;i++){
            if(i%2) tp++;
            a[i]=tp;
        }
        if(x>=d-p){
            int t=d-x;
            for(int i=1;i<=n;i++)
                if(a[i]>d-x) a[i]=++t;
        }
        else {
            a[n]=n/2-(d-p-x);
            int t=a[n-1]+d-p-x;
            for(int i=n-1;t>a[i-1]&&t>1;i--)
                a[i]=t--;
        }
        for(int i=n;i>=1;i--)
            cout<<a[i]<<" ";
    }
    return 0;
}

这样即可通过此题。