【解題】Zerojudge j180: 戰備存糧 (Food)

發布於 更新於 分類於 ， 閱讀次數： 文章字數： 424 所需閱讀時間 ≈ 2 分鐘

題目連結

j180: 戰備存糧 (Food)

我的想法

這題比較有趣，也有點像貪婪，涉及到每次食物下次減少時，倉庫的個數也要減少到最佳狀況（把倉庫減少當成守衛減少）。可以直接看我程式碼應該會比較好理解。

舉例

1
3 4

這筆測資食物總共有 12 個。

第一天減少 3 個（倉庫當前數量；守衛數量）：12 - 3 = 9

確認剩下的食物是否可以塞進小於等於當前倉庫數量的大小（每次減少 -1）：(3 - 1) * 4 = 8

9 <= 8 所以今天先不減小

第二天減少 3 個（倉庫當前數量；守衛數量）：9 - 3 = 6

確認剩下的食物是否可以塞進小於等於當前倉庫數量的大小（每次減少 -1）：(3 - 1) * 4 = 8

6 <= 8 所以今天倉庫數量減至 2

第三天減少 2 個（倉庫當前數量；守衛數量）：6 - 2 = 4

確認剩下的食物是否可以塞進小於等於當前倉庫數量的大小（每次減少 -1）：(2 - 1) * 4 = 4

4 <= 4 所以今天倉庫數量減至 1

最後四天相同做法（也可以判斷數量為 1 時，剩下食物個數加上前面 n 天之後，直接輸出 3 + 4 = 7 天，不過應該不影響答案）

參考解答

j180
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int a, b;
    vector<pair<int, int>> depositary;
    while (cin >> a) {
        if (a == -1) break;
        cin >> b;
        depositary.push_back(make_pair(a, b));
    }
    for (int i = 0; i < depositary.size(); i++) {
        int days = 0;
        int food = depositary[i].first * depositary[i].second;
        while (food != 0) {
            food -= depositary[i].first;
            days++;
            while (food <= (depositary[i].first - 1) * depositary[i].second) {
                depositary[i].first--;
            }
        }
        cout << days << "\n";
    }
    return 0;
}