#D. 贪吃蛇 (Greedy Snake)

    传统题 2000ms 256MiB

贪吃蛇 (Greedy Snake)

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

There are nn snake on the grass, numbered from 11 to nn, respectively. At the begining, stamina of each snake is aia_i. We call the snake numbered xx stronger than the one with number yy if its current stamina is greater than the other one (ax>aya_x > a_y), or ax=aya_x = a_y and x>yx > y.

Then, these snakes will have a duel. The duel will continue for several rounds. In each round, the strongest snake will have two options:

  1. It will eat the weakest snake and its stamina will decreased by the stamina of that weakest snake. The eaten snake will be removed from the duel.
  2. It won't eat any snake, the duel will end immediately.

Each snake wants to maximize the number of snake they eat without being eaten (obviously, snakes won't eat themselves).

Suppose every snake is smart enough, calculate the number of snake left after the duel.

This problem has multiple sets of data. For the first set of data, the stamina of each snake will be given in the input. For each subsequent set of data, some snakes' stamina will be changed.

Input Format

The first line contains an integer TT, the number of dataset.
The following line contains a single integer nn, the number of snakes.
The third line will contains exactly nn integers, the ii-th number represents the ii-th snake's initial stamina.
The next T3T - 3 lines contains T1T - 1 dataset, each dataset will have the following format:

  • One line contains an integer kk, the number of snakes whose stamina will be changed.
  • One line contains 2k2k integers and every two integers form a pair (x,y)(x, y) which means that the snake number xx's stamina will become yy.

Output Format

Print exactly TT lines, each represents the number of snakes left after the duel ends with the data provides in the ii-th dataset.

2
3
11 14 14
3
1 5 2 6 3 25
3
1
2
5
13 31 33 39 42
5
1 7 2 10 3 24 4 48 5 50
5
3

Sample 3

See attached files snakes3.in and snakes3.in

Sample 4

See attached files snakes4.in and snakes4.in

Constraints

For 20%20\% of data, n=3n=3.
For 40%40\% of data, n10n \le 10.
For 55%55\% of data, n2×103n \le 2 \times 10^3.
For 70%70\% of data, n5×104n \le 5 \times 10^4.
For 100%100\% of data, $3 \le n \le 10^6, 1 \le T \le 10, 0 \le k \le 10^5, 0 \le a_i, y \le 10^9$.
It's guaranteed that in every dataset, aia_i will be arranged in non-decreasing order.

CSP-S 模拟赛

未参加
状态
已结束
规则
OI
题目
4
开始于
2023-10-16 18:00
结束于
2023-10-16 22:06
持续时间
4.1 小时
主持人
参赛人数
13