← 返回题目列表

Codeforces · 2059/C

C. 客户服务

中文机器翻译题面 查看原题

Nikyr 已开始在“Black Contour”公司担任队列经理。他需要选择为客户提供服务的顺序。总共有 $$$n$$$ 个队列,每个队列最初包含 $$$0$$$ 人。在接下来的 $$$n$$$ 时刻,有两个连续事件:

1. 所有队列都有新顾客到达。更正式地说,在第 $$$j$$$ 个时刻,第 $$$i$$$ 队列中的人数增加了正整数 $$$a_{i,j}$$$。
2. Nikyr 恰好选择了当时要服务的 $$$n$$$ 队列之一。该队列中的顾客数量变为$$$0$$$。

设所有事件发生后第 $$$i$$$ 队列中的人数为 $$$x_i$$$。 Nikyr 希望 $$$x_1, x_2, \ldots, x_n$$$ 集合中的 MEX$$$^{\dagger}$$$ 尽可能大。帮助他确定通过最佳的队列服务顺序可以实现的最大价值。

$$$^{\dagger}$$$整数集合 $$$c_1, c_2, \ldots, c_k$$$ 的最小排除 (MEX) 被定义为集合 $$$c$$$ 中不出现的最小非负整数 $$$y$$$。

例如:

- $$$\operatorname{MEX}([2,2,1])= 0$$$,因为 $$$0$$$ 不属于该数组。
- $$$\operatorname{MEX}([3,1,0,1]) = 2$$$,因为 $$$0$$$ 和 $$$1$$$ 属于数组,但 $$$2$$$ 不属于该数组。
- $$$\operatorname{MEX}([0,3,1,2]) = 4$$$,因为 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$ 属于该数组,但 $$$4$$$ 不属于该数组。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 300$$$) — 队列数和时刻数。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 包含 $$$n$$$ 整数 $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) —每个时刻第 $$$i$$$ 个队列。

保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - $$$\operatorname{MEX}([x_1, x_2, \ldots, x_n])$$$ 可以达到的最大值。

示例

输入 #1

4
2
1 2
2 1
2
10 10
10 10
3
2 3 3
4 4 1
2 1 1
4
4 2 2 17
1 9 3 1
5 5 5 11
1 2 1 1

输出 #1

2
1
3
3

注意

在第一个测试用例中,第二个队列可以在时间 $$$1$$$ 提供服务,第一个队列可以在时间 $$$2$$$ 提供服务。第一个队列中将剩下 $$$x_1 = 0$$$ 人,第二个队列中将剩下 $$$x_2 = 1$$$ 人。因此,答案是 $$$\operatorname{MEX}([0, 1]) = 2$$$。

在第二个测试用例中,第一个队列可以被服务两次。第一个队列中将剩下 $$$x_1 = 0$$$ 人,第二个队列中将剩下 $$$x_2 = 20$$$ 人。因此,答案是 $$$\operatorname{MEX}([0, 20]) = 1$$$。

在第三个测试用例中,第三个队列可以在时间 $$$1$$$ 提供服务,第二个队列可以在时间 $$$2$$$ 提供服务,第一个队列可以在时间 $$$3$$$ 提供服务。第一个队列中将有 $$$x_1 = 0$$$ 人,第二个队列中将有 $$$x_2 = 1$$$ 人,第三队列中将有 $$$x_3 = 2$$$ 人。因此,答案是 $$$\operatorname{MEX}([0, 1, 2]) = 3$$$。