1310 - LỰA CHỌN ĐỘI TUYỂN ICPC

CLB Olympic Tin học HUTECH muốn lựa chọn các đội tuyển để tham gia vòng loại ICPC 2023. Mỗi đội bao gồm 3 sinh viên, và mỗi sinh viên chỉ có thể tham gia trong 1 đội. Hiệu suất của một đội được tính bằng điểm của sinh viên có điểm cao thứ hai trong đội. Mục tiêu là lựa chọn K đội sao cho tổng hiệu suất của các đội là lớn nhất.

Để giải bài toán này, solution sử dụng một kỹ thuật thông dụng trong lập trình thi đấu, đó là sắp xếp và lựa chọn.

Cụ thể, đây là cách solution hoạt động:

• Đọc số lượng sinh viên N và số lượng đội cần lựa chọn K.
• Đọc điểm của mỗi sinh viên và lưu vào một vector.
• Sắp xếp vector theo thứ tự giảm dần. Điều này đảm bảo rằng sinh viên có điểm cao nhất sẽ ở vị trí đầu tiên trong vector.
• Tính tổng hiệu suất của K đội được lựa chọn. Điều này được thực hiện bằng cách lựa chọn sinh viên có điểm cao thứ hai từ mỗi đội. Nhờ việc đã sắp xếp vector, chúng ta có thể chắc chắn rằng sinh viên này sẽ ở vị trí i \times 2+1 trong vector (với i là số đội).
• Xuất tổng hiệu suất của K đội.
• Điều quan trọng là chỉ số i \times 2+1 sẽ lấy điểm của sinh viên đứng thứ hai trong mỗi đội (nếu coi đội được sắp xếp theo thứ tự giảm dần về điểm số).
• Một điều nữa là solution kiểm tra điều kiện if(k * 3 <= n), để đảm bảo rằng số lượng sinh viên đủ để tạo thành K đội. Nếu không đủ, chương trình sẽ xuất ra kết quả là 0, vì không thể lựa chọn bất kỳ đội nào.

Mã nguồn tham khảo:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
       cin >> a[i];
    }
    sort(a.rbegin(), a.rend()); 
   
    long long ans = 0;
    int cnt = 0;
    if(k * 3 <= n) 
    {
	    for (int i = 0; i < k; i++) 
		{
			ans = ans + a[i*2+1];
	    }
	}
    cout <<  ans;
    return 0;
}