這是一款在 2007 年 PSP 上推出的遊戲
遊戲內容大略是:
你是魔王所崇拜的破壞神,由於未來會有許多勇者去迷宮中鬧事,所以你必須培養魔物以及設計迷宮去幹掉這些囂張的勇者,以保護住在迷宮中的魔王
但在資源有限的情況下,你除了鞏固迷宮的複雜程度以及魔物的強度,還得考慮這幾天勇者們的出征順序
魔王女兒知道這幾天可能會有哪些勇者闖入迷宮
她告訴你這些勇者的強度 $p_i$ 以及耐力 $s_i$
而你知道勇者們攻擊魔物的順序和魔物們的強度 $a_j$
每天,只會有一位勇者闖入迷宮,他會依序挑戰剩下的魔物 (也就是當已經有 $k$ 個魔物死去,那麼勇者會從第 $k+1$ 個魔物下手)
而勇者與一個魔物決鬥會有兩種結果:
在魔物被擊敗後,勇者能繼續挑戰下個魔物也可離開迷宮,每挑戰一個魔物就會耗損 $1$ 點耐力,當耐力歸零,勇者會離開迷宮
你得算出勇者最少會花幾天消滅迷宮中的所有魔物,以便設計更好的迷宮
第一列給定 $n$ 表示迷宮中有多少魔物 ($1 \le n \le 2\cdot 10^ 5$)
接著依照魔物被攻擊順序有 $n$ 個數字 $a_j$,表示魔物的強度 ($1 \le a_j \le 10^ 9$)
第三列給定 $m$ 表示幾個勇者想闖入迷宮 ($1 \le m \le 2\cdot 10^ 5$)
接著有 $m$ 對數字 $p_i, s_i$ 表示勇者強度以及耐力 ($1 \le p_i \le 10^ 9, 1 \le s_i \le n$)
保證 $n+m \le 2\cdot 10^ 5$
輸出一個數字表示勇者最少花幾天能清除迷宮中所有魔物
若沒辦法清除所有魔物則輸出 $-1$
第一筆測資,可能的勇者順序為:
第 $1$ 天:第一個勇者清掉 $2$ 個魔物
第 $2$ 天:第二個勇者清掉 $1$ 個魔物
第 $3$ 天:第二個勇者清掉 $1$ 個魔物
第 $4$ 天:第一個勇者清掉 $1$ 個魔物
第 $5$ 天:第二個勇者清掉 $1$ 個魔物
(再次闖入迷宮的勇者,耐力已經回復至初始值)
隔了十年後出了V!勇者のくせになまいきだR (VR専用)
優良遊戲,各位可以去玩玩看
PIXIV: 63322644
Codeforces 1257D Yet Another Monster Killing Problem
No. | Testdata Range | Score |
---|---|---|
1 | 0~82 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 500 | 65536 | 65536 | |
1 | 500 | 65536 | 65536 | |
2 | 500 | 65536 | 65536 | |
3 | 500 | 65536 | 65536 | |
4 | 500 | 65536 | 65536 | |
5 | 500 | 65536 | 65536 | |
6 | 500 | 65536 | 65536 | |
7 | 500 | 65536 | 65536 | |
8 | 500 | 65536 | 65536 | |
9 | 500 | 65536 | 65536 | |
10 | 500 | 65536 | 65536 | |
11 | 500 | 65536 | 65536 | |
12 | 500 | 65536 | 65536 | |
13 | 500 | 65536 | 65536 | |
14 | 500 | 65536 | 65536 | |
15 | 500 | 65536 | 65536 | |
16 | 500 | 65536 | 65536 | |
17 | 500 | 65536 | 65536 | |
18 | 500 | 65536 | 65536 | |
19 | 500 | 65536 | 65536 | |
20 | 500 | 65536 | 65536 | |
21 | 500 | 65536 | 65536 | |
22 | 500 | 65536 | 65536 | |
23 | 500 | 65536 | 65536 | |
24 | 500 | 65536 | 65536 | |
25 | 500 | 65536 | 65536 | |
26 | 500 | 65536 | 65536 | |
27 | 500 | 65536 | 65536 | |
28 | 500 | 65536 | 65536 | |
29 | 500 | 65536 | 65536 | |
30 | 500 | 65536 | 65536 | |
31 | 500 | 65536 | 65536 | |
32 | 500 | 65536 | 65536 | |
33 | 500 | 65536 | 65536 | |
34 | 500 | 65536 | 65536 | |
35 | 500 | 65536 | 65536 | |
36 | 500 | 65536 | 65536 | |
37 | 500 | 65536 | 65536 | |
38 | 500 | 65536 | 65536 | |
39 | 500 | 65536 | 65536 | |
40 | 500 | 65536 | 65536 | |
41 | 500 | 65536 | 65536 | |
42 | 500 | 65536 | 65536 | |
43 | 500 | 65536 | 65536 | |
44 | 500 | 65536 | 65536 | |
45 | 500 | 65536 | 65536 | |
46 | 500 | 65536 | 65536 | |
47 | 500 | 65536 | 65536 | |
48 | 500 | 65536 | 65536 | |
49 | 500 | 65536 | 65536 | |
50 | 500 | 65536 | 65536 | |
51 | 500 | 65536 | 65536 | |
52 | 500 | 65536 | 65536 | |
53 | 500 | 65536 | 65536 | |
54 | 500 | 65536 | 65536 | |
55 | 500 | 65536 | 65536 | |
56 | 500 | 65536 | 65536 | |
57 | 500 | 65536 | 65536 | |
58 | 500 | 65536 | 65536 | |
59 | 500 | 65536 | 65536 | |
60 | 500 | 65536 | 65536 | |
61 | 500 | 65536 | 65536 | |
62 | 500 | 65536 | 65536 | |
63 | 500 | 65536 | 65536 | |
64 | 500 | 65536 | 65536 | |
65 | 500 | 65536 | 65536 | |
66 | 500 | 65536 | 65536 | |
67 | 500 | 65536 | 65536 | |
68 | 500 | 65536 | 65536 | |
69 | 500 | 65536 | 65536 | |
70 | 500 | 65536 | 65536 | |
71 | 500 | 65536 | 65536 | |
72 | 500 | 65536 | 65536 | |
73 | 500 | 65536 | 65536 | |
74 | 500 | 65536 | 65536 | |
75 | 500 | 65536 | 65536 | |
76 | 500 | 65536 | 65536 | |
77 | 500 | 65536 | 65536 | |
78 | 500 | 65536 | 65536 | |
79 | 500 | 65536 | 65536 | |
80 | 500 | 65536 | 65536 | |
81 | 500 | 65536 | 65536 | |
82 | 500 | 65536 | 65536 |