Nội dung Bài tập
- Mã:
- HonestCoach
- Tên:
- Huấn luyện viên trung thực
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Nguồn bài tập:
- codeforces
- Link nguồn:
- https://codeforces.com/co...
- Được tạo bởi:
- o0Phong0o
Có n vận động viên trước mặt bạn. Các vận động viên được đánh số từ 1 đến n từ trái sang phải. Bạn biết sức mạnh của từng vận động viên - vận động viên số i có sức mạnh si.
Quảng cáo
Bạn muốn chia tất cả các vận động viên thành hai đội. Mỗi đội phải có ít nhất một vận động viên và mỗi vận động viên chỉ ở trong một đội.
Bạn muốn chênh lệch sức mạnh của vận động viên mạnh nhất từ đội thứ nhất với vận động viên yếu nhất từ đội thứ hai là ít nhất. Cụ thể là, bạn muốn chia các vận động viên thành hai đội A và B sao cho giá trị |max(A) − min(B)| càng nhỏ càng tốt, trong đó max(A) là sức mạnh cao nhất của một vận động viên từ đội A và min(B) là sức mạnh thấp nhất của một vận động viên từ đội B.
Ví dụ: nếu n = 5 và sức mạnh của các vận động viên là s = [3,1,2,6,4], thì một trong những trường hợp có thể được chia thành 2 đội là:
- đội thứ nhất: A = [1,2,4],
- đội thứ hai: B = [3,6].
Trong trường hợp này, giá trị |max(A) − min(B)| sẽ bằng |4 − 3| = 1. Ví dụ này minh họa một trong những cách phân chia tối ưu thành hai đội.
Yêu cầu: Xuất giá trị nhỏ nhất |max(A) − min(B)|.
Input
Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 1000) - số lượng testcase đầu vào. Sau đó t testcase tiếp theo.
Mỗi testcase bao gồm 2 dòng.
Dòng đầu tiên chứa số nguyên dương n (2 ≤ n ≤ 50) - số lượng vận động viên.
Dòng thứ hai chứa n số nguyên dương s1, s2,..., sn (1 ≤ si ≤ 1000), trong đó si - là sức mạnh của vận động viên thứ i. Lưu ý rằng các giá trị s có thể giống nhau.
Output
Đối với mỗi testcase, in một số nguyên - giá trị nhỏ nhất |max(A) − min(B)| với cách phân chia tối ưu tất cả các vận động viên thành hai đội.
Ví dụ:
Input
Output
5
5
3 1 2 6 4
6
2 1 3 2 4 3
4
7 9 3 1
2
1 1000
3
100 150 200
1
0
2
999
50
Giải thích
Testcase đầu tiên đã được giải thích ở trên. Trong testcase thứ 2, một trong những cách chia tối ưu là A=[2,1], B=[3,2,4,3], nên đáp án là |2−2|= 0.
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
THPT_NK_DEQUY
#include <iostream>using namespace std;int main(){ cout << "Co ga...