f443 - 商品擺設 Merchandise
題目描述
題目給定一串商品的擺設順序，其中 -1 代表空位。目標是將商品重新擺設，使得每個 -1 空位兩側的商品數值最大化。具體來說，對於每個空位，找到其左右兩側商品中數值最大和最小的商品，然後交換它們的位置。
解題思路
這題的核心思想是貪心演算法。對於每個空位，我們需要找到其左右兩側的最大值和最小值，並進行交換。這樣可以盡可能地使空位兩側的商品數值更大，從而達到最佳的擺設效果。
程式碼首先讀取商品的初始擺設順序，然後遍歷陣列，找到所有的空位。對於每個空位，程式碼會找到其左右兩側的最大值和最小值，並交換它們的位置。最後，程式碼輸出重新擺設後的商品順序。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int a[31][2],n;
int main(){
cin >> n;
for(int i=0;i<n;++i)
cin >> a[i][0];
for(int i=0;i<n;++i)
cin >> a[i][1];
int l=-1,r=-1;
for(int i=0;i<n;++i){
if(a[i][0]==-1){
l=r;
r=i;
if(l!=-1&&r!=-1&&r-l>2){
int ma=-101,mait,mi=101,mit;
for(int j=l+1;j<r;++j){
if(a[j][0]>ma){
ma=a[j][0];
mait=j;
}
if(a[j][0]<mi){
mi=a[j][0];
mit=j;
}
}
swap(a[mait][0],a[mit][0]);
swap(a[mait][1],a[mit][1]);
}
}
}
for(int i=0;i<n;++i)
cout << a[i][1] << " ";
}