Friends and the Restaurant

题意翻译

给出长度为 $n$ 的数组 $x$ 和 $y$，你可以从中选出一些数，且将这些数分为若干组，求最大组数满足每组的数量至少为 $2$ 且每组中 $x$ 的总和不大于 $y$ 的总和。 By BotDand

题目描述

A group of $ n $ friends decide to go to a restaurant. Each of the friends plans to order meals for $ x_i $ burles and has a total of $ y_i $ burles ( $ 1 \le i \le n $ ). The friends decide to split their visit to the restaurant into several days. Each day, some group of at least two friends goes to the restaurant. Each of the friends visits the restaurant no more than once (that is, these groups do not intersect). These groups must satisfy the condition that the total budget of each group must be not less than the amount of burles that the friends in the group are going to spend at the restaurant. In other words, the sum of all $ x_i $ values in the group must not exceed the sum of $ y_i $ values in the group. What is the maximum number of days friends can visit the restaurant? For example, let there be $ n = 6 $ friends for whom $ x $ = \[ $ 8, 3, 9, 2, 4, 5 $ \] and $ y $ = \[ $ 5, 3, 1, 4, 5, 10 $ \]. Then: - first and sixth friends can go to the restaurant on the first day. They will spend $ 8+5=13 $ burles at the restaurant, and their total budget is $ 5+10=15 $ burles. Since $ 15 \ge 13 $ , they can actually form a group. - friends with indices $ 2, 4, 5 $ can form a second group. They will spend $ 3+2+4=9 $ burles at the restaurant, and their total budget will be $ 3+4+5=12 $ burles ( $ 12 \ge 9 $ ). It can be shown that they will not be able to form more groups so that each group has at least two friends and each group can pay the bill. So, the maximum number of groups the friends can split into is $ 2 $ . Friends will visit the restaurant for a maximum of two days. Note that the $ 3 $ -rd friend will not visit the restaurant at all. Output the maximum number of days the friends can visit the restaurant for given $ n $ , $ x $ and $ y $ .

输入输出格式

输入格式

The first line of the input contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases in the test. The descriptions of the test cases follow. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 10^5 $ ) — the number of friends. The second line of each test case contains exactly $ n $ integers $ x_1, x_2, \dots, x_n $ ( $ 1 \le x_i \le 10^9 $ ). The value of $ x_i $ corresponds to the number of burles that the friend numbered $ i $ plans to spend at the restaurant. The third line of each test case contains exactly $ n $ integers $ y_1, y_2, \dots, y_n $ ( $ 1 \le y_i \le 10^9 $ ). The value $ y_i $ corresponds to the number of burles that the friend numbered $ i $ has. It is guaranteed that the sum of $ n $ values over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, print the maximum number of days to visit the restaurant. If friends cannot form even one group to visit the restaurant, print 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

说明

The first test case in explained in the problem statement. In the second test case, friends cannot form at least one group of two or more people. In the third test case, one way to visit the restaurant in one day is to go in a group of all three friends ( $ 1+3+10 \ge 2+3+7 $ ). Note that they do not have the option of splitting into two groups.

**题意翻译**

给定长度为 $ n $ 的数组 $ x $ 和 $ y $，你可以从中选出一些数，并将这些数分为若干组，求最大组数满足每组的数量至少为 2 且每组中 $ x $ 的总和不大于 $ y $ 的总和。

**题目描述**

一个有 $ n $ 个朋友的群体决定去一家餐厅。每个朋友计划花费 $ x_i $ 布雷斯来点餐，并且总共有 $ y_i $ 布雷斯 ($ 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 $ 布雷斯，他们的总预算是 $ 5+10=15 $ 布雷斯。因为 $ 15 \ge 13 $，他们实际上可以组成一组。
- 第二天，下标为 2、4、5 的朋友可以组成第二组。他们将在餐厅花费 $ 3+2+4=9 $ 布雷斯，他们的总预算将是 $ 3+4+5=12 $ 布雷斯（$ 12 \ge 9 $）。

可以证明他们将无法形成更多组，使得每组至少有两个朋友且每组都能支付账单。

所以，朋友们最多可以分成 2 组。朋友们最多会在两天内访问餐厅。注意，第三个朋友根本不会去餐厅。

输出给定 $ 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 $ 的朋友计划在餐厅花费的布雷斯数。

每个测试用例的第三行包含 $ n $ 个整数 $ y_1, y_2, \dots, y_n $（$ 1 \le y_i \le 10^9 $）。$ y_i $ 的值对应于编号为 $ i $ 的朋友拥有的布雷斯数。

保证所有测试用例的 $ 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
```**题意翻译** 给定长度为 $ n $ 的数组 $ x $ 和 $ y $，你可以从中选出一些数，并将这些数分为若干组，求最大组数满足每组的数量至少为 2 且每组中 $ x $ 的总和不大于 $ y $ 的总和。 **题目描述** 一个有 $ n $ 个朋友的群体决定去一家餐厅。每个朋友计划花费 $ x_i $ 布雷斯来点餐，并且总共有 $ y_i $ 布雷斯 ($ 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 $ 布雷斯，他们的总预算是 $ 5+10=15 $ 布雷斯。因为 $ 15 \ge 13 $，他们实际上可以组成一组。 - 第二天，下标为 2、4、5 的朋友可以组成第二组。他们将在餐厅花费 $ 3+2+4=9 $ 布雷斯，他们的总预算将是 $ 3+4+5=12 $ 布雷斯（$ 12 \ge 9 $）。 可以证明他们将无法形成更多组，使得每组至少有两个朋友且每组都能支付账单。 所以，朋友们最多可以分成 2 组。朋友们最多会在两天内访问餐厅。注意，第三个朋友根本不会去餐厅。 输出给定 $ 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 $ 的朋友计划在餐厅花费的布雷斯数。 每个测试用例的第三行包含 $ n $ 个整数 $ y_1, y_2, \dots, y_n $（$ 1 \le y_i \le 10^9 $）。$ y_i $ 的值对应于编号为 $ i $ 的朋友拥有的布雷斯数。 保证所有测试用例的 $ 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 ```