AT1984 Wide Swap

題意翻譯

給出一個元素集合為\(\{1,2,\dots,N\}(1\leq N\leq 500,000)\)的排列\(P\)，當(dāng)有\(i,j(1\leq i<j\leq N)\)滿足\(j-i\geq K\)\((1\leq K\leq N-1)\)且\(|P_{i}-P{j}|=1\)時，可以交換\(P_{i}\)和\(P_{j}\)

求：可能排列中字典序最小的排列

輸入格式：

\(N\) \(K\)

\(P_{1}\) \(P_{2}\) \(\dots\) \(P_{N}\)

---

這題目真是好思路啊。

首先，一個元素有兩個屬性，稱為權(quán)值\(p\)和位置\(l\)，交換的過程可以定義為固定權(quán)值交換位置，或者固定位置交換權(quán)值。

發(fā)現(xiàn)原本題目中的條件不好操作，于是把權(quán)值和位置交換意義，那么問題就變成了：

讓權(quán)值較小的盡可能呆在前面，當(dāng)兩個元素相鄰并且權(quán)值之差不小于\(k\)時，可以交換這兩個權(quán)值的位置。

我們把權(quán)值當(dāng)成固有屬性，拿位置去交換，那么如果兩個元素的權(quán)值之差小于\(k\)，那么它們的相對位置是不會改變的，我們對這一對按原有位置連一條有向邊。

對整個圖都這么連，然后以\(\tt{topo}\)序為第一關(guān)鍵字，權(quán)值為第二關(guān)鍵字跑優(yōu)先隊列\(\tt{topo}\)排序，就可以找到轉(zhuǎn)換以后的字典序了。

但是發(fā)現(xiàn)這樣連邊是\(O(n^2)\)的，過不了這個題，得想辦法優(yōu)化一下連邊。

考慮一個點\(i\)會向之后的哪些點連邊，\(\tt{Ta}\)會連接權(quán)值在\([p_i-k+1,p_i+k-1]\)內(nèi)的所有邊，而\(k\)是不變的。所以我們只需要連接\(\tt{Ta}\)位置上第一個大于\(\tt{Ta}\)和第一個小于\(\tt{Ta}\)的邊就可以了，其余的這兩個點會連上。

發(fā)現(xiàn)可以用線段樹維護(hù)，倒序加點，對權(quán)值建樹，區(qū)間查詢最小位置。

復(fù)雜度：\(O(nlogn)\)

---

Code:

#include <cstdio> #include <cstring> #include <queue> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define lb(a) lower_bound(a) #define is(a) insert(a) #define ps(a) push(a) const int N=5e5+10; const int inf=0x3f3f3f3f; int in[N],loc[N],p[N],ans[N],tot,n,k; std::priority_queue <int,std::vector<int>,std::greater<int> > q; int head[N],to[N<<1],Next[N<<1],cnt; void add(int u,int v) {to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt; } #define ls id<<1 #define rs id<<1|1 int min(int x,int y){return x<y?x:y;} int max(int x,int y){return x>y?x:y;} int mi[N<<2]; void change(int id,int l,int r,int p,int d) {if(l==r) {mi[id]=d;return;}int mid=l+r>>1;if(p<=mid) change(ls,l,mid,p,d);else change(rs,mid+1,r,p,d);mi[id]=min(mi[ls],mi[rs]); } int query(int id,int L,int R,int l,int r) {if(mi[id]==inf) return inf;if(l==L&&r==R) return mi[id];int Mid=L+R>>1;if(r<=Mid) return query(ls,L,Mid,l,r);else if(l>Mid) return query(rs,Mid+1,R,l,r);else return min(query(ls,L,Mid,l,Mid),query(rs,Mid+1,R,Mid+1,r)); } int main() {scanf("%d%d",&n,&k);rep(i,1,n) scanf("%d",p),p[p[0]]=i;memset(mi,0x3f,sizeof(mi));dep(i,n,1){int loc=query(1,1,n,p[i],min(n,p[i]+k-1));if(loc!=inf) add(p[i],p[loc]),++in[p[loc]];loc=query(1,1,n,max(1,p[i]-k+1),p[i]);if(loc!=inf) add(p[i],p[loc]),++in[p[loc]];change(1,1,n,p[i],i);}rep(i,1,n) if(!in[i]) q.ps(i);while(!q.empty()){int now=q.top();ans[now]=++tot;q.pop();for(int i=head[now];i;i=Next[i]){int v=to[i];--in[v];if(!in[v]) q.ps(v);}}rep(i,1,n) printf("%d\n",ans[i]);return 0; }

---

2018.10.26

轉(zhuǎn)載于:https://www.cnblogs.com/butterflydew/p/9854320.html

總結(jié)

以上是生活随笔為你收集整理的AT1984 Wide Swap的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。