分数: 350 点
问题陈述
有 N 驯鹿和一辆雪橇。的 i第-头驯鹿有重量 W_i 和实力 P_i.
对于每头驯鹿,选择“拉雪橇”或“骑雪橇”。 这里,拉动雪橇的驯鹿的总力量必须大于或等于乘坐雪橇的驯鹿的总重量。 雪橇上最多可以乘坐多少只驯鹿?
你被给予 T 测试用例。解决它们中的每一个。 一个输入文件中最多包含
约束
- 1\leq T\leq 10^5
- 1\leq N\leq 3\times 10^5
- 1\leq W_i,P_i\leq 10^9
- 所有输入值均为整数。
- 总和 N 在一个输入文件中最多 3\times 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N W_1 P_1 W_2 P_2 \vdots W_N P_N
输出
输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 3 3 1 4 1 5 9 5 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 10 133180711 458704923 531424946 225863856 141986070 637075158 500770732 289806469 502866767 408857335 559714289 569084545 287444582 992432993 559747907 753133304 432846188 949871298 727072164 756020367
示例输出 1
2 0 6
对于第一个测试用例,如果第 3 只驯鹿拉雪橇,第 1 只和第 2 只驯鹿乘坐雪橇,则驯鹿拉雪橇的总力量为 P_3=9,骑在雪橇上的驯鹿的总重量为 W_1+W_2=7,满足条件。由于并非所有驯鹿都能乘坐雪橇,所以答案是 2.