Editorial for Thần bài người Italy
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Spoiler Alert
Hint 1
- Sắp xếp lại mảng
Nếu như dãy nhận \(k\) phần tử cuối cùng liền sau nhau. Ta thay lá nhỏ nhất trong \(k\) lá đó bằng lá liền trước nó
Ngược lại, ta sẽ chọn vị trí phù hợp nhất không thuộc các giá trị liền nhau và thay lá nhỏ nhất bằng lá đó
Hint 2
Mình không rõ nếu bài này chặt nhị phân được không, nhưng thay vì sài
std::sort()bạn có thể dùng đếm phân phối trong \(O(n)\) vì \(1 \leq a_i \leq n\)
Reference AC code | \(O(n\) \(log_2n)\) time | \(O(n)\) auxiliary space | Greedy
C++
int main()
{
/// Input
int n = readInt();
int k = readInt();
ll sum = 0;
vector<int> a(k);
for (int &x : a) {
cin >> x;
sum += x;
}
sort(all(a));
int amin = a.front();
if (amin + k == n + 1) /// Khi dãy giảm dần đều từ n, chỉ có thể chọn số bé hơn
return cout << sum - 1, 0; /// Thay lá nhỏ nhất bằng lá bé hơn: ai - 1
for (int i = n, j = k - 1; i >= 0; --i, --j)
if (j == 0 || i != a[j]) /// Chọn giá trị phù hợp tối đa có thể thay thế
return cout << sum - a.front() + i, 0; /// Thay lá nhỏ nhất bằng lá lớn hơn: i
return 0;
}
Comments