令\(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)\),考虑优化。每个点只需要连向左右最小的满足条件的数即可,其它的边实际上不需要。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
// <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; } |
说点什么