Sunday 5 January 2020

SMPAIR - Cặp có tổng nhỏ nhất


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

Popular posts