昨天晚上巨困，就沒有打，今天課間的時候就看了一下D題，發現好像可以瞎搞，于是吃完飯就寫了一下，調過樣例一次就A了qaq。

D. Sequence and Swaps

枚舉+貪心
由于數據范圍$n\le 500$，由此我們可以在$n^3$完成此題。

最后完成所有操作后，我們手中肯定還有一個數，我們考慮去枚舉這個數。

最后手里的數一定不在最終的排列中，于是用一個數組b[]把除了手中的數記錄下來，不難發現只要排序一下這個所有數的位置就確定了。

而且不難發現如果當前手中的數是$x$，我們必須一次將他歸位，于是就模擬操作，每次找出現在手中的數在b[]數組中的位置（注意重復的數只需要開一個st[]數組記錄一下即可），然后看看能不能執行交換操作，把過程模擬一邊，順便記錄次數。

模擬過程中，如果當前手中的數已經是枚舉剩余的數之間跳出循環，如果不能交換說明不合法也直接跳出循環。

最后再判斷一下是否滿足條件即可。

時間復雜度$O(n^3)$

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=510; int a[N],b[N],c[N]; bool st[N]; int main() {IO;int T=1;cin>>T;while(T--){int n,x;cin>>n>>x;for(int i=1;i<=n;i++) cin>>a[i];bool fl=1;for(int i=2;i<=n;i++)//特判最后手中的數是 x 也就是不用操作if(a[i]<a[i-1]) fl=0;if(fl) {cout<<0<<'\n';continue;}a[n+1]=x;int res=0x3f3f3f3f;for(int i=1;i<=n;i++)// 枚舉剩下的數是a[i]{for(int j=1;j<=n;j++){if(i==j)b[j]=x;elseb[j]=a[j];}sort(b+1,b+1+n);int tmp=x;memcpy(c,a,sizeof c);bool ok=1;int cnt=0;for(int j=1;j<=n;j++){memset(st,0,sizeof st);int k;for(k=1;k<=n;k++)// 找到當前手中的數應該所在的位置{if(b[k]==tmp&&c[k]!=tmp){while(st[k]||c[k]==tmp) k++;st[k]=1;break;}}if(c[k]>tmp) // 能不能執行交換操作{swap(c[k],tmp);cnt++;if(tmp==a[i]) break;//手中的數已經是枚舉的數}else// 交換失敗{ok=0;break;}}for(int i=2;i<=n;i++)if(c[i]<c[i-1]) ok=0;if(a[i]!=tmp) ok=0;// 最后手中的數tmp一定要等于枚舉的數a[i]if(ok) res=min(res,cnt);}if(res==0x3f3f3f3f) cout<<-1<<'\n';else cout<<res<<'\n';}return 0; }

感覺應該有復雜度更優的做法，但是我這個做法若優化感覺十分難寫~~

要加油哦~

總結

以上是生活随笔為你收集整理的codeforces1455 D. Sequence and Swaps的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。