AT_agc058_e [AGC058E] Nearer Permutation 题解

nkrqzjc_zzz · 2024-01-18 10:58:10 · 题解

题目链接

题目思路

为方便起见，指数和数值均以 0 为基础。

首先，让我们考虑如何找到 f(x)。

让 z=x 作为初始解决方案，让我们尝试从左到右决定 z 中的项。在条件 d(x,z) \leq d(y,z) 下，我们应该将一个尽可能小的值移到开头。最后，我们有下面的算法（下面称为算法 A ），其中 Invs 是 x 的反转数。

• 设 result=(),s=Invs/2。
• 执行下面的操作 N 次。
• 设 x_m 是 x_0,x_1,\cdots,x_{\min(\lfloor s\rfloor,N-1)} 中的最小值。
• 将 x_m 附加到 result 的末尾。
• 从 x 中删除 x_m。
• 设 s=s-m。
• 返回 result。

取最小的索引 k，使得 A_k>A_{k+1}。如果没有这样的 k，答案显然是 Yes。

从上面操作的执行方式可以看出，执行操作 k 次后会具有以下属性：

• 如果 A_{k+1} 从 x 中删除，A_k,A_{k+2},A_{k+3},\cdots,A_{N-1} 将按此顺序排列。

因此，可以看出，满足 f(x)=A 的排列 x 仅限于通过以下过程获得的排列。

• 设 B=A。
• 对于 i=k+1,k-1,k-2,\cdots,0，执行以下操作。
• 将 B_i 向右移动。更准确地说，将 B_i,B_{i+1},\cdots,B_{i+t} 更改为 B_{i+1},\cdots,B_{i+t},B_i，其中 t 是移动的长度。这里，B_i<B_{i+j}（1\leq j\leq t）必须保持（在操作之前）。此外，如果 i=k+1，则 A_k<B_{i+j} 必须存在。

对于每个 i，设 c_i 为 B_i 的移动长度。应该调整 c_i，使程序返回所需的输出。

在执行操作 k+1 次操作之后，考虑值 A_{k+1} 的位置 p 与值 s 的差 v=s-p。

首先，考虑 i\neq k+1 的情况。如果 c_i 增加 1，则 s 的初始值将增加 \frac{1}{2}，并且在第 i 次操作中选择的 m 的值将增加 1，因此 s 将总共减少 \frac{1}{2}，v 将依次减少 \frac{1}{2}。

在 i=k+1 的情况下，s 的初始值将增加 \frac{1}{2}，p 的值将增加 1，因此 v 将减少 \frac{1}{2}。

毕竟，无论哪种情况，v 都将减少 \frac{1}{2}。设 S 是 A 的反转数。如果所有的 c_i 都是 0，那么我们有 v=\frac{S}{2}，并且 v 的期望值是 0 或 \frac{1}{2}，所以我们可以看到 c_i 的总和应该是 S 或 S-1。

现在，让我们尝试这两个值。（事实上，仅考虑 S-1 就够了。）

由于 c_i 的和是已知的，因此 x 的反转数也是已知的。在这里，如果按照 A_i 的升序决定 c_i 的值，那么使它们尽可能大的贪心策略就会成功地工作。这是因为我们可以将不符合这一方法的解决方案转变为符合这一方法的解决方案。省略了证明的小细节，这是一个简单的个案分析。

如果在根据上述策略决定 c_i 时存在矛盾，或者总和没有达到预定目标，则答案为 No；否则为 Yes。

该方法的时间复杂度为 O(N\log N)。

代码

码风稍稍有点差，见谅！

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define int ll
template<class t,class u> bool m(t&a,u b){if(b<a){a=b;return 1;}else return 0;}
template<class t> using v=vector<t>;
using o=v<int>;
o rv(int n,int f=0){
    int j;o v(n);
    for(int i=0;i<n;i++)scanf("%lld",&j),v[i]=j+f;
    return v;
}
template<class t>
struct g{
    int s;v<t> e;
    g(int n=0){it(n);}g(const v<t>&a){it(a);}
    void it(int n){e.clear();e.resize(s=n);}
    void it(const v<t>&a){
        s=si(a);
        e.resize(s);
        for(int i=0;i<s;i++)e[i]=a[i];
        for(int i=0;i<s;i++){
            int j=i+(i+1)&(-i-1);
            if(j<s)e[j]+=e[i];
        }
    }
    void ad(int i,t v){
        for(;i<s;i+=(i+1)&(-i-1))e[i]+=v;
    }
    t ge(int i){
        t r=t();
        for(;i>=0;i-=(i+1)&(-i-1))r+=e[i];
        return r;
    }
    t d(int b,int e){
        return ge(e-1)-ge(b-1);
    }
};
int xu(o q){
    int n=int(q.size()),d=0;
    g<int> y(n);
    for(int i=0;i<n;i++)d+=i-y.ge(q[i]),y.ad(q[i],1);
    return d;
}
bool er(const o&p){
    int n=int(p.size()),k=-1,h;
    for(int i=n-1;i>=0;i--)if(p[i]>p[i+1])k=i;
    if(k==-1)return 1;
    o q(n);for(int i=0;i<n;i++)q[p[i]]=i;
    h=xu(p);
    auto w=[&](int d){
        int s=(h+d)>>1,r=n;
        for(int v=0;v<p[k];v++){
            if(v==p[k+1]){
                for(int i=k+2;i<n;i++)if(p[i]<p[k])m(r,i);
                int u=min(r-q[v]-1,d);
                d-=u;m(r,k+1+u);
            }else if(q[v]<k){
                if(r<n&&r-q[v]<=s)return false;
                int u=min(r-q[v]-1,d);
                d-=u;s-=u;
            }else m(r,q[v]);
        }
        return d==0;
    };
    for(int i=h-1;i<h+1;i++)if(w(i))return true;
    return false;
}
int s,t;
main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&s);
        o p=rv(s,-1);
        if(er(p))puts("Yes");else puts("No");
    }
}

管理员朋友辛苦了！