P7435 - Boring Task

内存限制：128 MB 时间限制：5 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：0 通过：0

You are given N tasks numbered from 1 to N and a single machine able to process the tasks. At any time, the machine can only process a single task.

For every integer i between 1 and N, you are given 2 integers -

Ti, denoting when the

ith task is created, that means you can only process the

ith task not earlier than

Ti, and

Di, denoting the period of time the machine takes to completely process the

ith task.

All the tasks are individual, so you can assign tasks in any order. Also, if the machine starts to process a task, then it never stops working until the task is finished. The machine can immediately start the other task (obviously, this task should be available) after finishing a task.

The waiting time, for the

ith task, is defined as the delay time of the task that is equal to the difference between the time when the machine starts to process the

ith task and

Ti. You want to minimize the maximum waiting time of the given tasks. Find the minimum value of maximum waiting time.

The first line of the input contains a single integer T (1≤T≤1 200), the number of test cases. Each test case consists of 3 lines.
The first line of each test case contains a single integer N (1≤N≤

2⋅105), the number of tasks. The next line contains N integers

Ti (1≤

Ti≤

2⋅1014), the earliest time the

ith task can be processed. The

3rd line N integers

Di (1≤

Di≤

109), the period of time the machine takes to finish the

ith task. It’s guaranteed that the sum of N over all test cases doesn’t exceed 2 500 000.

For each test case, you should print the minimum possible value of the maximum waiting time.

0
2

2020 Multi-University Training Contest 1

7435: Boring Task

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签