a362 - 1. 搬雕像
題目描述
題目要求計算將 n 個雕像按照高度和重量重新排序，並放置到編號為 1 到 n 的收藏台上所需的最短搬運距離。雕像的排序規則是：高度由低到高，高度相同則重量由輕到重。搬運距離定義為每個雕像從其原始位置到其目標位置的距離之和，相鄰收藏台的距離為 1 公尺。
解題思路
解題思路是先對雕像進行排序，按照題目要求的條件（高度升序，高度相同則重量升序）。然後計算每個雕像從其原始位置到排序後位置的距離，將所有距離加總即可得到最短搬運距離。這裡使用 bubble sort 進行排序，然後計算每個雕像的移動距離。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
struct a{
int no;
int h;
int w;
};
bool cmp(a x,a y){
return x.h < y.h || ((x.h==y.h)&&(x.w<=y.w));
}
int main(){
int n;
while(cin >> n){
a b[n];
for(int i=0;i<n;i++){
b[i].no=i;
cin >> b[i].h >> b[i].w;
}
for(int i=0;i<n;i++){
for(int j=0;j<n-i-1;j++){
if(!cmp(b[j], b[j+1]))
swap(b[j], b[j+1]);
}
}
int ans=0;
for(int i=0;i<n;i++)
ans+=abs(b[i].no-i);
cout << ans << "\n";
}
}