TA的每日心情 | 鬱悶 2015-2-10 21:23 |
---|
簽到天數: 1 天 [LV.1]初來乍到
高級會員
- 積分
- 779
|
本帖最後由 amoshuangyc 於 2014-4-28 22:09 編輯
今天面試完心情不錯,看到這題心血來潮就寫了一下,嗯嗯,總是在畢業前對資訊社有了一點貢獻。
順便試一下這裡的發文系統~~
這題我是直接把所有可能都跑一遍,反正也才 6 個可能:"BCG", "BGC", "CBG", "CGB", "GBC", "GCB"。
以 Sample Input: 5 10 5 20 10 5 10 20 10 為例, 編號 | Brown(B) | Green(G) | Clear(C) | 1 | 5 | 10 | 5 | 2 | 20 | 10 | 5 | 3 | 10 | 20 | 10 |
我們嘗試計算組合 BGC 所需移動的步數:
第一個桶子最終為 B,第二個為 G,第三個為 C,
那我們需要做的是
- 將第二個桶子的 B 和第三個桶子的 B 都移到第一個桶子。
- 將第一個桶子的 G 和第三個桶子的 G 都移到第二個桶子。
- 將第一個桶子的 C 和第二個桶子的 C 都移到第三個桶子。
於是所需移動的步數為表格中的 (B2 + B3) + (G1 + G3) + (C1 + C2) = 75。
當我們把各個組合都計算過後,我們就可以知道哪一個組合所需移動的步數最小。這題答案是 CBG 50。
※ 桶子的 index 轉為從 0 開始數
#include <iostream>
using namespace std;
int calculate_steps(const int data[][3], const string combination) {
int steps = 0;
for (int i=0; i<3; i++) {
if (combination == 'B')
steps = steps + (data[(i+1)%3][0] + data[(i+2)%3][0]);
else if (combination == 'G')
steps = steps + (data[(i+1)%3][1] + data[(i+2)%3][1]);
else // combination = 'C'
steps = steps + (data[(i+1)%3][2] + data[(i+2)%3][2]);
}
return steps;
}
int main() {
const string combinations[6] = {"BCG", "BGC", "CBG", "CGB", "GBC", "GCB"};
int data[3][3]; // [[B0, G0, C0], [B1, G1, C1], [B2, G2, C2]]
while (cin >> data[0][0] >> data[0][1] >> data[0][2]
>> data[1][0] >> data[1][1] >> data[1][2]
>> data[2][0] >> data[2][1] >> data[2][2]) {
int min_steps = calculate_steps(data, combinations[0]);
int min_idx = 0;
for (int i=1; i<6; i++) {
int steps = calculate_steps(data, combinations);
if (steps < min_steps) {
min_steps = steps;
min_idx = i;
}
}
cout << combinations[min_idx] << " " << min_steps << endl;
}
return 0;
}
|
評分
-
查看全部評分
|