c081 - 00102 - Ecological Bin Packing
題目描述
題目描述了三個桶子，每個桶子包含棕色、綠色和透明色玻璃瓶。目標是通過移動玻璃瓶，使每個桶子只包含單一顏色的玻璃瓶，並最小化移動的瓶子數量。如果有多個最小移動方案，則輸出字典順序最小的方案。
解題思路
這道題的解法是枚舉所有可能的桶子顏色分配方案，然後計算每種方案下需要移動的瓶子數量。由於只有三個桶子和三種顏色，所以只有 3! = 6 種可能的分配方案。對於每種方案，計算移動瓶子的數量，並找到最小的移動數量和對應的顏色分配方案。由於題目要求輸出字典順序最小的方案，因此在找到最小移動數量後，如果有多個方案達到這個數量，則選擇字典順序最小的方案。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
int a[3],b[3],c[3];
int main(){
while(cin >> a[0]){
cin >> a[1] >> a[2];
for(int i=0;i<3;++i)
cin >> b[i];
for(int i=0;i<3;++i)
cin >> c[i];
int ans,aB=a[1]+a[2],aG=a[0]+a[2],aC=a[0]+a[1],bB=b[1]+b[2],bG=b[0]+b[2],bC=b[0]+b[1],cB=c[1]+c[2],cG=c[0]+c[2],cC=c[0]+c[1];
ans=min(min(min(aB+bG+cC,aB+bC+cG),min(aG+bB+cC,aG+bC+cB)),min(aC+bG+cB,aC+bB+cG));
if(ans==aB+bC+cG)
cout << "BCG ";
else if(ans==aB+bG+cC)
cout << "BGC ";
else if(ans==aC+bB+cG)
cout << "CBG ";
else if(ans==aC+bG+cB)
cout << "CGB ";
else if(ans==aG+bB+cC)
cout << "GBC ";
else if(ans==aG+bC+cB)
cout << "GCB ";
cout << ans << "\n";
}
}