UVa 102 Ecological Bin Packing
解題策略
因為瓶子的顏色總共只有三種：B、G、C，所以直接手動將六種排列方式列出，並一一計算每種方法的移動次數即可。注意
本題的I/O量非常大，所以使用cin/cout與scanf/printf之間的速度差距很明顯。我解這題用cin/cout的執行時間是0.420秒，換為scanf/printf後的執行時間則是0.230秒，幾乎要快上一倍，cin之效能殺手令我印象深刻。碎碎念
這題花了不少時間debug，找到bug之後只有囧一個字可以形容，就是totalGlasses進迴圈前忘了歸零，栽在這種智障 bug上...。提醒我以後一定要謹守編程的好習慣: 「永遠在變數需要被用到的最內層區塊才宣告並初始化該變數。」
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * UVa 102 Ecological Bin Packing | |
| * Author: chchwy | |
| * Last Modified: 2008.09.10 | |
| * Tag: Adhoc | |
| */ | |
| #include<iostream> | |
| enum { B = 0, C = 1, G = 2 }; | |
| int main() | |
| { | |
| //六種排列組合 | |
| int binColor[][3] = { {B, C, G}, {B, G, C}, {C, B, G}, | |
| {C, G, B}, {G, B, C}, {G, C, B} | |
| }; | |
| char s[][4] = {"BCG", "BGC", "CBG", "CGB", "GBC", "GCB"}; | |
| int bin[3][3]; | |
| while (scanf("%d%d%d%d%d%d%d%d%d", | |
| &bin[0][B], &bin[0][G], &bin[0][C], | |
| &bin[1][B], &bin[1][G], &bin[1][C], | |
| &bin[2][B], &bin[2][G], &bin[2][C]) != EOF) | |
| { | |
| int currentMove = 0; | |
| int totalGlasses = 0; | |
| for (int i = 0; i < 3; i++) | |
| totalGlasses += (bin[i][B] + bin[i][G] + bin[i][C]); | |
| int minMove = totalGlasses; | |
| int minNo = 0; //第minNo號排列組合move最少 | |
| //六種排列組合都跑過一次 | |
| for (int i = 0; i < 6; i++) //移動的次數 = 總瓶數-不用移動的瓶數 | |
| { | |
| currentMove = totalGlasses | |
| - bin[0][binColor[i][0]] | |
| - bin[1][binColor[i][1]] | |
| - bin[2][binColor[i][2]]; | |
| if (currentMove < minMove) | |
| { | |
| minMove = currentMove; | |
| minNo = i; | |
| } | |
| } | |
| printf("%s %d\n", s[minNo], minMove); | |
| } | |
| return 0; | |
| } | |
留言
張貼留言