Tổng chênh lệch lớn nhất
Đề bài
Mô tả
Bạn được cho một dãy số gồm phần tử và truy vấn, mỗi truy vấn gồm hai số nguyên dương . Với mỗi truy vấn, xét dãy số , nhiệm vụ của bạn là sắp xếp lại dãy số theo thứ tự bất kỳ sao cho tổng chênh lệch của hai phần tử liên tiếp bất kỳ trong dãy là lớn nhất có thể. Hay nói cách khác, bạn cần tối đa hóa giá trị của .
Dữ liệu vào
- Dòng đầu tiên gồm hai số nguyên dương và tương ứng với số lượng phần tử trong dãy và số lượng truy vấn ().
- Dòng thứ hai gồm số nguyên dương tương ứng với giá trị của các phần tử trong dãy ().
- Cuối cùng là dòng, mỗi dòng gồm hai số nguyên dương mô tả các truy vấn ().
Dữ liệu ra
Với mỗi truy vấn, in ra kết quả trên một dòng là tổng chênh lệch tối đa có thể đạt được.
Ràng buộc
- .
- .
- .
Subtasks
- Subtask 1 ( số điểm): .
- Subtask 2 ( số điểm): .
- Subtask 3 ( số điểm): .
- Subtask 4 ( số điểm): với mọi từ đến .
- Subtask 5 ( số điểm): .
- Subtask 6 ( số điểm): Không có ràng buộc gì thêm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 2 1 2 3 4 8 1 5 1 3 |
17 3 |
Truy vấn 1: xếp thành , tổng . Truy vấn 2: xếp thành , tổng . |
| 6 3 5 1 9 2 6 7 1 6 2 6 3 3 |
27 25 0 |
Ví dụ bổ sung (không có trong đề gốc). Truy vấn 1: , tổng . Truy vấn 2: , tổng . Truy vấn 3: chỉ có một phần tử nên tổng bằng . |
Bình luận