Description

題目 PDF 檔在這裡

如果你玩過《世界計畫》,應該知道裡面有一些樂團,包括 Virtual Singers, Leo/need, Vivid Bad Squad, More More Jump, Wonderlands×Showtime 以及 Nightcord at 25:00

而其中可愛擔當毫無疑問絕對是 瑞希,如果你沒看過瑞希,在這裡讓你看看:

瑞希

瑞希超可愛的對吧!為了在夢裡都能見到瑞希,我決定要安排我的做夢時間,好讓我在夢裡都能見到瑞希。

假設第 $i$ 天的做夢時長是 $d_i$ 個小時,而如果那天不做夢的話 $d_i = 0$。瑞希總共會來 $k$ 次,可以選到任何一個還有空的晚上 (可以選到前面的),每次會待滿 $t_i$ 個小時。因為我太想趕快見到瑞希了,所以都會挑選滿足上述條件的時間中最早的。當一小段的夢境被排給瑞希後,剩餘的時間仍然是可以利用的。

然而,我現在被英文作業纏著脫不了身,你可以先幫我排排時程嗎?

Input Format

第一行有兩個數 $n, k$ 分別表示總共有 $n$ 天以及 $k$ 次排期。

第二行有 $n$ 個數,分別表示 $d_1, d_2, \ldots, d_i, \ldots, d_n$

第三行有 $k$ 個數,分別表示 $t_1, t_2, \ldots, t_i, \ldots, t_k$

$n, k \leq 2 \times 10^5$

$0 \leq d_i, t_i \leq 2^{31} - 1$

Output Format

請針對每一個 $t_i$ 輸出一個值,代表能排程的時間中最早的一天。

如果待不滿 $t_i$ 個小時請輸出 0。

Sample Input 1

8 5
3 2 4 1 5 5 2 6
4 4 7 1 1

Sample Output 1

3 5 0 1 1

Hints

瑞希很可愛

Problem Source

題序看不懂可以看這個 (?

#include <iostream>
using namespace std;

int d[200005], t[200005];

int main() {
        int n, k;
        cin >> n >> k;

        for (int i = 0; i < n; i++)
                cin >> d[i];
        for (int i = 0; i < k; i++)
                cin >> t[i];

        for (int i = 0; i < k; i++) {
                bool flag = 0;
                for (int j = 0; j < n; j++) {
                        if (d[j] >= t[i]) {
                                d[j] -= t[i];
                                cout << j + 1 << ' ';
                                flag = 1;
                                break;
                        }
                }
                if (flag) continue;
                cout << 0 << ' ';
        }
        return 0;
}



TopCoder

User's AC Ratio

25.0% (1/4)

Tags

Problem Setter

Subtasks

No. Testdata Range Constraints Score
1 0 範例側資 0
2 1~10 $n \leq 10 ^ 4$ 30
3 0~30 無特別限制 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 3
1 2000 524288 65536 2 3
2 2000 524288 65536 2 3
3 2000 524288 65536 2 3
4 2000 524288 65536 2 3
5 2000 524288 65536 2 3
6 2000 524288 65536 2 3
7 2000 524288 65536 2 3
8 2000 524288 65536 2 3
9 2000 524288 65536 2 3
10 2000 524288 65536 2 3
11 2000 524288 65536 3
12 2000 524288 65536 3
13 2000 524288 65536 3
14 2000 524288 65536 3
15 2000 524288 65536 3
16 2000 524288 65536 3
17 2000 524288 65536 3
18 2000 524288 65536 3
19 2000 524288 65536 3
20 2000 524288 65536 3
21 2000 524288 65536 3
22 2000 524288 65536 3
23 2000 524288 65536 3
24 2000 524288 65536 3
25 2000 524288 65536 3
26 2000 524288 65536 3
27 2000 524288 65536 3
28 2000 524288 65536 3
29 2000 524288 65536 3
30 2000 524288 65536 3