Link Sub: http://www.spoj.com/PTIT/problems/P155SUMI/
Người Gửi: Easylove
- Problem:
Cho dãy a[] có m phần tử. Chọn ra n phần tử sao cho với A là số lớn nhất trong n số, B là số nhỏ nhất trong n số thì hiệu A – B là nhỏ nhất trong các cách chọn ra n số.Input
Dòng đầu chứa 2 số nguyên n, m(2 <= n <= m <= 50)
Dòng thứ 2 chứa m số nguyên a[1], a[2],…, a[m](1 <= i <= m, 4 <= a[i] <= 1000)
Output
In ra hiệu nhỏ nhất tìm được.
Example:
In ra hiệu nhỏ nhất tìm được.
Input
2 10
4 5 6 7 8 9 10 11 12 12
Output:
0
- Solution:
- Đơn giản chỉ cần sắp xếp lại cho dãy tăng dần. (Vì m nhỏ bạn hoàn toàn có thể dùng SX nổi bọt, code dưới đây dùng SX trong thư viện STL)- Nhảy từng bước một: lấy số cuối (là số đầu +n-1) trừ số đầu và xác định hiệu min