Hướng dẫn cho Mua sách
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Spoiler Alert
Approach
- Sort giảm dần, lấy giá trị 2 cuốn rồi bỏ qua 1 cuốn
Đề yêu cầu: Cứ mỗi cặp 3 số mình sẽ lấy số nhỏ nhất bỏ đi, còn lại là tính tổng
Chứng minh: Cứ mỗi cặp \((a, b, c)\) và \((a \geq b \geq c)\) để mình lợi nhất thì \(c\) phải lớn nhất có thể. Mà nếu sắp xếp giảm dần thì mỗi cặp 3 số sẽ có \(c\) thỏa mãn
Question
- Liệu bài này có thể giải bằng quy hoạch động không ?
Reference AC code | \(O(n\) \(log_2n)\) time | \(O(n)\) auxiliary space | Sorting, Greedy
C++
int main()
{
int n = readInt();
vi a(n);
for (int &x : a) cin >> x;
sort(all(a), greater<int>());
ll res = 0;
for (int i = 0; i < n; i += 3)
res += a[i] + a[i + 1];
cout << res;
return 0;
}
Bình luận
10 diem!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!