Tóm tắt đề bài

Có \(N\) đảng tham gia bầu cử với tổng cộng \(V\) phiếu. Hiện tại đảng \(i\) đã có \(a_i\) phiếu. Số phiếu còn lại chưa kiểm là \(R = V - \sum a_i\). Bạn được phép phân phối \(R\) phiếu này cho các đảng tùy ý. Sau đó, \(M\) ghế được chia theo phương pháp D'Hondt:

1. Loại các đảng có số phiếu \(b_i < 5\% V\).
2. Với \(M\) ghế, mỗi lần chọn đảng có giá trị \(Q_i = \frac{b_i}{s_i + 1}\) lớn nhất để trao ghế (\(s_i\) là số ghế hiện tại của đảng \(i\)). Nếu \(Q_i\) bằng nhau, ưu tiên đảng có chỉ số \(i\) nhỏ hơn.

Yêu cầu: Tìm số ghế lớn nhất mà đảng \(X\) có thể nhận được.

Phân tích

• Điều kiện 5%: Một đảng chỉ được xét chia ghế nếu \(b_i \geq \frac{V}{20}\).
• Chiến thuật tối ưu: Để đảng \(X\) có nhiều ghế nhất, ta cần làm cho \(Q_X\) lớn nhất có thể và các \(Q_i\) khác nhỏ nhất có thể.
  • Cách tốt nhất là dồn toàn bộ số phiếu còn lại \(R\) cho đảng \(X\). Khi đó \(b_X = a_X + R\), và các đảng khác giữ nguyên số phiếu \(b_i = a_i\).
  • Việc dồn phiếu cho \(X\) giúp \(Q_X = \frac{b_X}{s_X + 1}\) đạt giá trị cực đại, đồng thời không làm tăng \(Q_i\) của bất kỳ đối thủ nào.
• Phương pháp D'Hondt: Đây là một quá trình tham lam. Tại mỗi bước trong \(M\) bước, ta chọn đảng có \(Q_i\) lớn nhất. Để mô phỏng hiệu quả, ta sử dụng một hàng đợi ưu tiên (Priority Queue).

Cách làm đơn giản (Brute Force)

Với các subtask nhỏ, ta có thể thử mọi cách chia phiếu còn lại. Tuy nhiên, dựa trên nhận xét tối ưu ở trên, ngay cả với subtask nhỏ, việc dồn hết phiếu cho \(X\) luôn là lựa chọn tốt nhất để tối đa hóa ghế cho \(X\).

Độ phức tạp

• Thời gian: \(O(M \cdot \log N)\) cho việc mô phỏng bằng Priority Queue.
• Đánh giá: Cách này thực tế đã khá tối ưu và có thể vượt qua hầu hết các test nếu cài đặt cẩn thận.

Hướng giải quyết (Tối ưu)

Thuật toán

1. Tính số phiếu còn lại: \(R = V - \sum_{i=1}^N a_i\).
2. Gán toàn bộ phiếu còn lại cho đảng \(X\): \(b_X = a_X + R\). Các đảng khác \(b_i = a_i\).
3. Lọc danh sách các đảng thỏa mãn điều kiện \(b_i \geq \frac{V}{20}\) (tương đương \(20 \cdot b_i \geq V\)).
4. Sử dụng một priority_queue để lưu trữ các đảng thỏa mãn điều kiện. Mỗi phần tử trong hàng đợi lưu:
   • Số phiếu \(b_i\).
   • Số ghế hiện tại \(s_i\).
   • Chỉ số của đảng \(id_i\).
5. Định nghĩa quy tắc so sánh trong priority_queue:
   • So sánh hai phân số \(\frac{b_1}{s_1 + 1}\) và \(\frac{b_2}{s_2 + 1}\) bằng cách nhân chéo: \(b_1 \cdot (s_2 + 1)\) so với \(b_2 \cdot (s_1 + 1)\).
   • Nếu hai giá trị bằng nhau, đảng có chỉ số \(id\) nhỏ hơn sẽ được ưu tiên (theo đề bài).
6. Lặp \(M\) lần:
   • Lấy đảng có \(Q_i\) lớn nhất ra khỏi hàng đợi.
   • Tăng số ghế của đảng đó lên 1.
   • Đẩy đảng đó trở lại hàng đợi với số ghế mới.
7. Kết quả là số ghế \(s_X\) của đảng \(X\).

Lưu ý về kiểu dữ liệu

• \(V\) có thể lên tới \(10^{12}\), nên các phép tính liên quan đến phiếu bầu và nhân chéo phải dùng kiểu số nguyên 64-bit (long long trong C++, int trong Python).

Độ phức tạp

• Thời gian: \(O(N + M \log N)\). Trong đó \(O(N)\) để đọc dữ liệu và lọc các đảng, \(O(M \log N)\) để thực hiện \(M\) lần lấy và đẩy vào hàng đợi ưu tiên.
• Bộ nhớ: \(O(N)\) để lưu trữ thông tin các đảng.

Code tham khảo

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

struct Node {
    long long b;
    int s, id;
};

// Cấu trúc so sánh để priority_queue ưu tiên Q_i lớn nhất
struct Compare {
    bool operator()(Node const& n1, Node const& n2) {
        long long left = n1.b * (n2.s + 1);
        long long right = n2.b * (n1.s + 1);
        if (left == right) {
            // Nếu Q_i bằng nhau, đảng có ID nhỏ hơn được ưu tiên
            // Trong priority_queue, return true nghĩa là n1 có ưu tiên thấp hơn n2
            return n1.id > n2.id;
        }
        return left < right;
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    long long V;
    int N, M, X;
    cin >> V >> N >> M >> X;

    vector<long long> a(N + 1);
    long long sum_a = 0;
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        sum_a += a[i];
    }

    // Dồn toàn bộ phiếu còn lại cho đảng X
    vector<long long> b = a;
    b[X] += (V - sum_a);

    priority_queue<Node, vector<Node>, Compare> pq;
    for (int i = 1; i <= N; i++) {
        // Điều kiện 5%: b_i / V >= 1/20 <=> 20 * b_i >= V
        if (b[i] * 20 >= V) {
            pq.push({b[i], 0, i});
        }
    }

    vector<int> seats(N + 1, 0);
    // Nếu đảng X không đủ 5%, nó sẽ nhận 0 ghế
    if (b[X] * 20 < V) {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 0; i < M; i++) {
        if (pq.empty()) break;
        Node top = pq.top();
        pq.pop();

        seats[top.id]++;
        top.s++;
        pq.push(top);
    }

    cout << seats[X] << endl;

    return 0;
}

import heapq

def solve():
    import sys
    input = sys.stdin.read
    data = input().split()

    if not data:
        return

    V = int(data[0])
    N = int(data[1])
    M = int(data[2])
    X = int(data[3])

    a = list(map(int, data[4:]))
    sum_a = sum(a)

    # Dồn toàn bộ phiếu còn lại cho đảng X
    b = list(a)
    b[X-1] += (V - sum_a)

    # Priority Queue trong Python là min-heap
    # Ta lưu (-Q_i, id) để mô phỏng max-heap
    # Vì so sánh phân số b/(s+1) khó, ta dùng một class hoặc lưu trực tiếp

    class Party:
        def __init__(self, b, s, id):
            self.b = b
            self.s = s
            self.id = id

        def __lt__(self, other):
            # So sánh b1/(s1+1) > b2/(s2+1)
            left = self.b * (other.s + 1)
            right = other.b * (self.s + 1)
            if left == right:
                return self.id < other.id # ID nhỏ hơn ưu tiên cao hơn
            return left > right # Q_i lớn hơn ưu tiên cao hơn

    pq = []
    for i in range(N):
        if b[i] * 20 >= V:
            heapq.heappush(pq, Party(b[i], 0, i + 1))

    seats = [0] * (N + 1)

    for _ in range(M):
        if not pq:
            break
        top = heapq.heappop(pq)
        seats[top.id] += 1
        top.s += 1
        heapq.heappush(pq, top)

    print(seats[X])

solve()