b373 - [福州19中]车厢重组
題目描述
題目要求計算將一組初始車廂順序，透過旋轉橋面（相當於交換相鄰兩節車廂）的方式，使其按照車廂號從小到大排列所需的最少步驟數。
解題思路
題目描述的旋轉橋面操作，實際上就是交換相鄰兩個元素。因此，問題可以簡化為計算將一個陣列排序成升序所需的最小交換次數。程式碼使用類似冒泡排序的邏輯來計算交換次數。每次遍歷陣列，如果發現相鄰兩個元素順序錯誤，就交換它們，並將交換次數加一。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int main(){
int a;
while(cin >> a){
int b[a],sum=0;
for(int i=0;i<a;i++)
cin >> b[i];
for(int i=0;i<a;i++){
for(int j=i+1;j<a;j++){
if(b[i]>b[j]){
b[i]=b[i]^b[j];
b[j]=b[i]^b[j];
b[i]=b[i]^b[j];
sum++;
}
}
}
cout << sum << "\n";
}
}