#PU1451. USACO 2024 December Contest, Gold — Problem 3. Job Completion

    ID: 1303 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:dec24来源:usaco.orgscoring:equal_test_cases贪心

USACO 2024 December Contest, Gold — Problem 3. Job Completion

USACO 2024 December Contest, Gold — Problem 3. Job Completion

题目描述

Bessie the cow has NN (1≤N≤2⋅1051\le N\le 2\cdot 10^5) jobs for you to potentially complete. The ii-th one, if you choose to complete it, must be started at or before time sis_i and takes tit_i time to complete (0≤si≤1018,1≤ti≤10180\le s_i\le 10^{18}, 1\le t_i\le 10^{18}). What is the maximum number of jobs you can complete? Time starts at 00, and once you start a job you must work on it until it is complete, without starting any other jobs in the meantime.

输入格式

The first line contains TT, the number of independent test cases (1≤T≤101\le T\le 10). Each test case is formatted as follows. The first line contains NN. Each of the next NN lines contains two integers sis_i and tit_i. Row i+1i+1 has the details for the iith job. It is guaranteed that the sum of NN over all test cases does not exceed 3⋅1053\cdot 10^5.

输出格式

For each test case, the maximum number of jobs you can complete, on a new line.

数据范围

Inputs 2: Within the same test case, all tit_i are equal. Inputs 3-4: N≤2000N\le 2000, si,ti≤2000s_i, t_i\le 2000 Inputs 5-8: N≤2000N\le 2000 Inputs 9-16: No additional constraints. Problem credits: Benjamin Qi

样例

样例 1

3
2
1 4
1 2
2
2 3
1 2
3
1 4
2 3
1 2
1
2
2
For the first test case, you can only complete one of the jobs. After completing
one job, it will then be time $2$ or later, so it is too late to start the other
job, which must be started at time $1$ or earlier.
For the second test case,  you can start the second job at time $0$ and finish
at time $2$,  then start the first job at time $2$ and finish at time $5$.