Giả sử chúng ta có một mảng A với n phần tử và một số m. Có n sinh viên tham gia kỳ thi. Điểm tối đa có thể đạt được là m. A[i] là điểm của sinh viên thứ i. Chúng ta có thể điều chỉnh điểm của từng sinh viên, nhưng phải thỏa mãn các điều kiện: điểm không vượt quá m, tất cả điểm đều là số nguyên và điểm trung bình của tất cả sinh viên không thay đổi. Nếu muốn tối đa hóa điểm của sinh viên đầu tiên, điểm cao nhất có thể gán là bao nhiêu?
Ví dụ, nếu đầu vào là A = [1, 2, 3, 4]; m = 10, thì đầu ra sẽ là 10, vì trung bình là 2.5, ta có thể đặt điểm thành [10, 0, 0, 0] nơi trung bình giữ nguyên nhưng điểm của người đầu tiên là lớn nhất.
Các bước thực hiện
Để giải quyết bài toán này, chúng ta thực hiện theo các bước sau:
sum := 0 n := kích thước của A for khởi tạo j := 0, khi j < n, cập nhật (tăng j lên 1), do: sum := sum + A[j] return minimum của m và sum
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; int solve(vector<int> A, int m){ int sum = 0; int n = A.size(); for (int j = 0; j < n; j++){ sum += A[j]; } return min(m, sum); } int main(){ vector<int> A = { 1, 2, 3, 4 }; int m = 10; cout << solve(A, m) << endl; }Đầu vào
{ 1, 2, 3, 4 }, 10Đầu ra
10