我的OI没救了 | 一道看起来简单想起来不简单的题目

Take_A_Single_6 · 2024-09-29 17:30:46 · 个人记录

题目描述

for(int i=1;i<=n;i++)
{
    for(int j=i+1;j<=n;j++)
    {
        if(a[i]>a[j])swap(a[i],a[j]);
        cnt++;
    }
}

给定 n,m 和初始排列 a ，求当 cnt=m 时的数组。

解题思路

很显然的思路是把完整的轮提出来，最后一轮如果不完整就暴力交换，难点在于快速求出提出前 k 个数后的数组。
分析每个数在什么时候被交换。对于每个大于 k 的 x 只会与 pos<pos_x 的数中第 i 小的交换，每一轮实质上就是找最初的一个下降子序列循环移位，如果选中了 x，显然 x 和后面一位的“缝隙”里的数都比二者大，所以下一次也一定会被选中。而且由于 x>k，交换不会停止，最终在所有 pos \le pos_x 的数中，x一定是第 k 小的。
从整体看，我们只需要维护最小的 k 个数即可。如果 a_i 比堆顶小，入堆，a_i \gets top，弹出堆顶，否则不变，考虑单调性，用桶维护即可。

代码分析

#include<bits/stdc++.h>
#define int long long
#define db double
#define maxn 1000005
#define mod 998244353
#define fir first
#define sec second
#define pr pair<int,int>
#define mk make_pair
#define inf 10000000000000000
using namespace std;
inline int read()
{
    int SS=0,WW=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')WW=-1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        SS=(SS<<1)+(SS<<3)+(ch^48);
        ch=getchar();
    }
    return SS*WW;
}
inline void write(int XX)
{
    if(XX<0)putchar('-'),XX=-XX;
    if(XX>9)write(XX/10);
    putchar(XX% 10 + '0');
}
int n,m,a[maxn],p,b[maxn],t;
signed main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(p=1;p<=n;p++)
    {
        if(m-(n-p)<0)break;
        else m-=(n-p);
    }//算轮数
    for(int i=1;i<p;i++)t=max(t,a[i]),b[a[i]]++,a[i]=i;//提出完整轮
    for(int i=p;i<=n;i++)
    {
        if(a[i]<t)
        {
            --b[a[i]],a[i]=t;
            while(!b[--t]);
        }//桶代替堆维护
    }
    for(int i=p+1;m;i++,m--)if(a[p]>a[i])swap(a[p],a[i]);//不完整轮暴力
    for(int i=1;i<=n;i++)write(a[i]),putchar(' ');
    return 0;
}