【AGC001F】Wide Swap – 徐亦轲的博客

令\(i\)的位置为\(Q_i\)：

从这个角度考虑问题和给定的操作，就是每次交换相邻的两个数，并且它们要满足差不小于\(k\)，使得最终\(1\)的位置尽量靠前，然后\(2\)的位置尽量靠前，依此类推。

可以发现差小于\(k\)的数的相对位置不会发生变化，并且满足这个条件的排列都是合法排列。

另外可以证明的是最小字典序的\(Q\)一定对应最小字典序的\(P\)。求出最小字典序后在\(i\)前面的数一定都是比\(i\)小或者比\(i\)大且差小于\(k\)且在原来\(Q\)中就在\(i\)前面的数。这样就保证了\(i\)在不比它小的数中尽可能靠前，就得到了最小字典序的\(P\)。

那么如果\(|i-j|<k\)并且\(P_i<P_j\)那么从\(i\)向\(j\)连边，求这张图的最小字典序拓扑排列即可。

边数\(O(n^2)\)，考虑优化。每个点只需要连向左右最小的满足条件的数即可，其它的边实际上不需要。

// <swap.cpp> - Mon Mar 27 20:17:23 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
#define next NEXT
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int MAXN=500010;
const int MAXM=1000010;
const int INF=1e9;
int bt,b[MAXN],next[MAXM],to[MAXM],d[MAXN];
inline void add(int x,int y){next[++bt]=b[x];b[x]=bt;to[bt]=y;d[y]++;}
int p[MAXN],q[MAXN];
set <int> s;
set <int>::iterator it;
priority_queue <int,vector<int>,greater<int> > r;
int main(){
    int n=gi(),k=gi();
    for(int i=1;i<=n;i++)q[p[i]=gi()]=i;
    for(int i=1;i<=n;i++){
        if(i>k)s.erase(p[i-k]);
        it=s.insert(p[i]).first;
        if(++it!=s.end())add(i,q[*it]);
    }
    s.clear();
    for(int i=n;i;i--){
        if(i+k<=n)s.erase(p[i+k]);
        it=s.insert(p[i]).first;
        if(++it!=s.end())add(i,q[*it]);
    }
    for(int i=1;i<=n;i++)if(!d[i])r.push(i);
    for(int i=1;i<=n;i++){
        int x=r.top();r.pop();
        p[x]=i;
        for(int j=b[x];j;j=next[j])if(!--d[to[j]])r.push(to[j]);
    }
    for(int i=1;i<=n;i++)printf("%d\n",p[i]);
    return 0;
}

// <swap.cpp> - Mon Mar 27 20:17:23 2017

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <set>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

#define next NEXT

template<typename T>

inline void gg(T &res){

res=0;T fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

res*=fh;

}

inline int gi(){int x;gg(x);return x;}

inline lol gl(){lol x;gg(x);return x;}

const int MAXN=500010;

const int MAXM=1000010;

const int INF=1e9;

int bt,b[MAXN],next[MAXM],to[MAXM],d[MAXN];

inline void add(int x,int y){next[++bt]=b[x];b[x]=bt;to[bt]=y;d[y]++;}

int p[MAXN],q[MAXN];

set <int> s;

set <int>::iterator it;

priority_queue <int,vector<int>,greater<int> > r;

int main(){

int n=gi(),k=gi();

for(int i=1;i<=n;i++)q[p[i]=gi()]=i;

for(int i=1;i<=n;i++){

if(i>k)s.erase(p[i-k]);

it=s.insert(p[i]).first;

if(++it!=s.end())add(i,q[*it]);

}

s.clear();

for(int i=n;i;i--){

if(i+k<=n)s.erase(p[i+k]);

it=s.insert(p[i]).first;

if(++it!=s.end())add(i,q[*it]);

}

for(int i=1;i<=n;i++)if(!d[i])r.push(i);

for(int i=1;i<=n;i++){

int x=r.top();r.pop();

p[x]=i;

for(int j=b[x];j;j=next[j])if(!--d[to[j]])r.push(to[j]);

}

for(int i=1;i<=n;i++)printf("%d\n",p[i]);

return 0;

}

说点什么