← 返回题目列表

Codeforces · 1729/D

D. 朋友和餐厅

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

一群 $$$n$$$ 朋友决定去一家餐馆。每个朋友都计划点餐 $$$x_i$$$ burles,总共有 $$$y_i$$$ burles ($$$1 \le i \le n$$$)。

朋友们决定分几天去餐厅。每天,至少有两个朋友组成的一群人去餐厅。每个朋友访问餐厅的次数不超过一次(也就是说,这些组不相交)。这些团体必须满足一个条件,即每个团体的总预算必须不少于团体中的朋友在餐厅消费的金额。换句话说,组中所有 $$$x_i$$$ 值的总和不得超过组中 $$$y_i$$$ 值的总和。

朋友最多可以光顾餐厅多少天?

例如,假设有 $$$n = 6$$$ 朋友,其中 $$$x$$$ = [$$$8, 3, 9, 2, 4, 5$$$] 且 $$$y$$$ = [$$$5, 3, 1, 4, 5, 10$$$]。然后:

- 第一个和第六个朋友可以在第一天去餐厅。他们将在餐厅花费$$$8+5=13$$$ burles,他们的总预算为$$$5+10=15$$$ burles。由于$$$15 \ge 13$$$,他们实际上可以组成一个团体。
- 指数为 $$$2, 4, 5$$$ 的朋友可以组成第二组。他们将在餐厅花费$$$3+2+4=9$$$ burles,他们的总预算将为$$$3+4+5=12$$$ burles ($$$12 \ge 9$$$)。

可以证明,他们将无法组建更多的群组,以便每个群组至少有两个朋友,并且每个群组都可以支付账单。

因此,朋友可以分成的最大组数是 $$$2$$$。朋友们最多可以在餐厅停留两天。请注意,$$$3$$$-rd 的朋友根本不会去这家餐厅。

输出给定 $$$n$$$、$$$x$$$ 和 $$$y$$$ 的情况下朋友可以光顾餐厅的最大天数。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。

测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 朋友的数量。

每个测试用例的第二行恰好包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le 10^9$$$)。 $$$x_i$$$ 的值对应于编号为 $$$i$$$ 的朋友计划在餐厅消费的 burles 数量。

每个测试用例的第三行恰好包含 $$$n$$$ 整数 $$$y_1, y_2, \dots, y_n$$$ ($$$1 \le y_i \le 10^9$$$)。值$$$y_i$$$对应于编号为$$$i$$$的朋友拥有的burles数量。

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

输出

对于每个测试用例,打印访问餐厅的最大天数。如果朋友无法组团去餐厅,请打印 0。

示例

输入 #1

6
6
8 3 9 2 4 5
5 3 1 4 5 10
4
1 2 3 4
1 1 2 2
3
2 3 7
1 3 10
6
2 3 6 9 5 7
3 2 7 10 6 10
6
5 4 2 1 8 100
1 1 1 1 1 200
6
1 4 1 2 4 2
1 3 3 2 3 4

输出 #1

2
0
1
3
1
3

注意

第一个测试用例在问题陈述中进行了解释。

在第二个测试用例中,朋友不能组成至少一个由两人或多人组成的小组。

在第三个测试用例中,一天内去餐厅的一种方法是与所有三个朋友一起去($$$1+3+10 \ge 2+3+7$$$)。请注意,他们无法选择分成两组。