Bạn được cho một dãy số a[1], a[2], ... , a[N]. Tìm tổng nhỏ nhất của ai + aj, với 1 < i < j <= N.
Input: Dòng đầu tiên chứa một số nguyên T là số bộ test. Mỗi bộ test được miêu tả như sau:
Dòng đầu tiên của mỗi bộ test là số nguyên N - số phần tử của dãy số a.
Dòng tiếp theo lần lượt là các số a[1], a[2], ..., a[N], mỗi số cách nhau một dấu cách.
Output: Với mỗi bộ test, in ra màn hình một số nguyên duy nhất là kết quả của bộ test.
Ràng buộc:
- T = 10^5, N = 2: 13 điểm
- T = 10^5, 2 <= N <= 10: 16 điểm
- T = 1000, 2 <= N <= 100: 31 điểm
- T = 10, 2 <= N <= 10^5: 40 điểm
- 1 <= a[i] <= 10^6
Solution: phương pháp tham lam. Sắp xếp dãy a theo thứ tự tăng dần, tổng của 2 phần tử đầu tiên (cũng là 2 phần tử nhỏ nhất) là kết quả.
Code mẫu (C++):
No comments:
Post a Comment