Next Nest

wusa!~(•㉨•)

「題解】食堂打飯

发表于 Valine：

QUST 2020級第三學期算法數據結構測試 Contest1029 T3

Problem Description

$m$ 名同學按順序從 $1$ 到 $m$ 編號， $k$ 號同學的飯盒容量為 $z_k$ 。先有1到 $m$ 號同學開始打飯。某名同學 $l$ 打完容量為 $z_l$ 的飯後，下一名排隊同學 $i$ 馬上接替 $l$ 同學的位置開始打飯。即 $l$ 同學第 $x$ 秒結束時完成打飯，則 $i$ 同學第 $x + 1$ 秒立刻開始打飯。若當前打飯人數 $n$ 小於 $m$ ，則只有 $n$ 個打飯窗口開放，其它 $n - m$ 個關閉。問所有同學都打完飯需要多少秒時間。

Inputs

輸入數據的第1行是2個整數 $m$ 和 $n$ $(1 \leq m \leq 10000, 1 \leq n \leq 100, 且 n \leq m)$ ，用一個空格隔開，分別表示打飯人數和打飯窗口個數。
第2行 $m$ 個整數 $z_1, z_2, …, z_m$ ，其中 $z_k$ 表示 $k$ 號同學的飯盒容量，且 $1 \leq z_k \leq 100$ 。

Outputs

輸出只有一行，為一個整數，表示所需的總時間。

Samples

  • Sample #1

    • Inputs (輸入)

      1
      2
      5 3
      4 4 1 2 1

    • Outputs (輸出)

      1
      4

    • Explanations (解釋)

      第1秒，3人打飯。第1秒結束時，1、2、3號同學每人的已打飯量為1，3號同學打飯完成，4號同學接替3號同學開始打飯。
第2秒，3人打飯。第2秒結束時，1、2號同學每人的已打飯量為2，4號同學的已打飯量為1。
第3秒，3人打飯。第3秒結束時，1、2號同學每人的已打飯量為3，4號同學的已打飯量為2。4號同學打飯完成，5號同學接替4號同學開始打飯。
第4秒，3人打飯。第4秒結束時，1、2號同學每人的已打飯量為4，5號同學的已打飯量為1。1、2、5號同學打飯完成，即所有人完成打飯。
總打飯時間為4秒。

  • Sample #2

    • Inputs (輸入)

      1
      2
      10 3
      6 3 3 10 3 1 5 2 2 7

    • Outputs (輸出)

      1
      18

Analysis

1
2
3
4
5
6
7
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;
using namespace __gnu_cxx;

筆者個人認為這道題是一道純粹的模擬題目，模擬題的噁心之處就在於你沒有任何一種固定的算法或數據結構模板能夠直接套在這個問題上。
越是複雜的模擬，越是無法三言兩語說清楚，只能一步一步慢慢講。
除了題目輸入的三種變量 $m, n, \{z_k\}_{k=1}^m$ 之外，我們額外設置一個變量task[]來記錄並實時模擬每個窗口處理當前任務的時間進度，以及變量res[]來記錄花費的總時間。

1
int m, n, z[10001], task[101], res = 0;

然後在程式起手時完成數據與變量的輸入

1
2
3
4
int main(int argc, char *argv[]) {
    scanf("%d %d", &m, &n);
    for (int k = 0; k != m; ++k)
        scanf("%d", &z[k]);

初始時刻，前n個人類會排滿n個窗口 (=・ω・=)

1
2
for (int k = 0; k != n; ++k)
    task[k] = z[k];

另外，我們要用一個指針，在還在排隊的人們之中，記錄下一個辦理業務的人

1
int nextone = n;

接下來我們將逐時刻模擬各個窗口的進度，且每一時刻我們要檢查每個窗口的進度

1
2
3
for (res = 0; ; ++res) {
    bool flag = false;
    for (int k = 0; k != n; ++k) {

在上述三行中，我們定義了一個變量flag，接下來會把其用於檢查任務完成情況 _(:з」∠)_

1
2
3
4
5
6
7
8
9
10
11
12
13
if (task[k] > 0)
    // 如若這個窗口還沒結束任務，那麼任務的進度+1，剩餘進度-1，亦即--task[k]
    --task[k];
if (!task[k] && nextone != m)
    // 如若這個窗口的任務恰好在剛才(即此時刻)結束，
    //   如若後面還有人排隊(亦即 nextone != m)，
    // 則該窗口加入排隊的第一個人的任務
    task[k] += z[nextone++];
if (task[k])
    // 如若這個窗口還有任務，那麽flag設爲真，
    // 這樣一來如若某個窗口的task[k]==0，那麽就意味著它後面也沒有任務追加，
    //   從而這個窗口該的任務徹底結束
    flag = true;

根據上面所説，如若flag不爲真，那麽就意味著模擬結束，可以在此時刻終結循環啦 XD

1
2
3
4
    }
    if (!flag)
        break;
}

輸出結果並結束程式 _(≧∇≦」∠)_

1
2
3
    printf("%d\n", ++res);
    return 0;
}

這道題主要就是，逐時刻逐窗口模擬，實時檢查完成情況。

Solution Program

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;
using namespace __gnu_cxx;

int m, n, z[10001], task[101], res = 0;

int main(int argc, char *argv[]) {
    scanf("%d %d", &m, &n);
    for (int k = 0; k != m; ++k)
        scanf("%d", &z[k]);
    if (m <= n) {
        // 排隊人數 <= 窗口個數 的情況，但根據題意並不需要，
        // 這裡算是筆者考試時候不審題想多了... qvq
        int curmax = 0;
        for (int k = 0; k != m; ++k)
            if (z[k] > curmax)
                curmax = z[k];
        printf("%d\n", curmax);
    } else {
        // 初始化: n個窗口為人類1~n排隊
        for (int k = 0; k != n; ++k)
            task[k] = z[k];
        // 用於標記下一個需要排隊的人類的指針
        int nextone = n;
        for (res = 0; ; ++res) {
            bool flag = false;
            for (int k = 0; k != n; ++k) {
                if (task[k] > 0)
                    --task[k];
                if (!task[k] && nextone != m)
                    task[k] += z[nextone++];
                if (task[k])
                    flag = true;
            }
            if (!flag)
                break;
        }
        printf("%d\n", ++res);
    }
    return 0;
}

Complexity Analysis

  • 空間複雜度: 本題目水到不需要動態數組，因此空間複雜度為O(1)。

  • 時間複雜度: 最壞情況下，本解法的時間複雜度可能上升至 $O(m^2)$ 。