有N個瓶子，編號 1 ~ N，放在架子上。


比如有5個瓶子：
2 1 3 5 4


要求每次拿起2個瓶子，交換它們的位置。
經(jīng)過若干次后，使得瓶子的序號為：
1 2 3 4 5


對于這么簡單的情況，顯然，至少需要交換2次就可以復位。


如果瓶子更多呢？你可以通過編程來解決。


輸入格式為兩行：
第一行: 一個正整數(shù)N（N<10000）, 表示瓶子的數(shù)目
第二行：N個正整數(shù)，用空格分開，表示瓶子目前的排列情況。


輸出數(shù)據(jù)為一行一個正整數(shù)，表示至少交換多少次，才能完成排序。


例如，輸入：
5
3 1 2 5 4


程序應該輸出：
3


再例如，輸入：
5
5 4 3 2 1


程序應該輸出：
2


資源約定：
峰值內(nèi)存消耗 < 256M
CPU消耗 ?< 1000ms


請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內(nèi)容。


所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。


注意: main函數(shù)需要返回0
注意: 只使用ANSI C/ANSI C++ 標準，不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。
注意: 所有依賴的函數(shù)必須明確地在源文件中 #include <xxx>， 不能通過工程設(shè)置而省略常用頭文件。


提交時，注意選擇所期望的編譯器類型。

思路：剛開始想到的是逆序數(shù)，但是看到第三個案例時就放棄了。然后是貪心，如果第i個位置 a[i] 的值不是 i ,那么就把 i 的值換回來，這個可以在輸入時預處理一下，標記第 i 個值即 a[i] 在數(shù)組下標的哪個位置，然后在此循環(huán)交換就可以了,O(n)的復雜度。

代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<cstring> #include<algorithm> #include<cmath> #define M 10000+5 using namespace std;int a[M];//原數(shù)組 int v[M];//標記數(shù)組 int main(){int n; while(scanf("%d",&n)!=EOF){int ans=0;for(int i=1; i<=n; ++i){scanf("%d",&a[i]);v[a[i]]=i;//預處理 }for(int i=1; i<=n; ++i){if(a[i]!=i){swap(a[i],a[v[i]]);++ans;}}printf("%d\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【蓝桥杯】 交换瓶子的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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