Hướng dẫn cho Thần bài người Italy

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.

Authors: SPyofgame

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;
}

Bình luận

Không có bình luận nào.