Greedy? 贪婪的算法

Question

Problem Description
iSea is going to be CRAZY! Recently, he was assigned a lot of works to do, so many that you can't imagine. Each task costs Ci time as least, and the worst news is, he must do this work no later than time Di!
OMG, how could it be conceivable! After simple estimation, he discovers a fact that if a work is finished after Di, says Ti, he will get a penalty Ti - Di. Though it may be impossible for him to finish every task before its deadline, he wants the maximum penalty of all the tasks to be as small as possible. He can finish those tasks at any order, and once a task begins, it can't be interrupted. All tasks should begin at integral times, and time begins from 0.

Input
The first line contains a single integer T, indicating the number of test cases.
Each test case includes an integer N. Then N lines following, each line contains two integers Ci and Di.

Technical Specification
1. 1 <= T <= 100
2. 1 <= N <= 100 000
3. 1 <= Ci, Di <= 1 000 000 000

Output
For each test case, output the case number first, then the smallest maximum penalty.

Sample Input
2
2
3 4
2 2
4
3 6
2 7
4 5
3 9

Sample Output
Case 1: 1
Case 2: 3

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

To solve this problem, we can sort the tasks by their deadlines in ascending order. Then, we can iterate through the tasks in this order and calculate the penalty if we finish each task after its deadline. We keep track of the maximum penalty seen so far and output it as the smallest maximum penalty for the test case. Here is the Python code to solve the problem:

# Function to calculate the smallest maximum penalty for a test case
def calculate_smallest_max_penalty(tasks):
    tasks.sort(key=lambda x: x[1])  # Sort tasks by deadline
    max_penalty = 0
    total_time = 0
    
    for task in tasks:
        ci, di = task
        total_time += ci
        penalty = max(0, total_time - di)
        max_penalty = max(max_penalty, penalty)
    
    return max_penalty
# Main function to process input and output results
def main():
    t = int(input())
    
    for case in range(1, t+1):
        n = int(input())
        tasks = []
        
        for _ in range(n):
            ci, di = map(int, input().split())
            tasks.append((ci, di))
        
        result = calculate_smallest_max_penalty(tasks)
        print(f"Case {case}: {result}")
if __name__ == "__main__":
    main()

Sample Input:

2
2
3 4
2 2
4
3 6
2 7
4 5
3 9

Sample Output:

Case 1: 1
Case 2: 3