Editorial for election: Bầu cử tổng thống

Hiểu bài toán

Bài toán yêu cầu xác định xem với ~n~ ứng cử viên (có số phiếu ban đầu là ~a_1, a_2, ..., a_n~) và ~k~ phiếu chưa bầu, chúng ta có thể phân phối ~k~ phiếu này sao cho tất cả các ứng cử viên đều có số phiếu bằng nhau hay không.

Điều kiện để tất cả ứng cử viên có số phiếu bằng nhau:

1. Tổng số phiếu cuối cùng (~Tổng phiếu ban đầu + k~) phải chia hết cho ~n~ (số ứng cử viên). Nếu không chia hết, không thể chia đều.
2. Số phiếu mục tiêu (sau khi chia đều) phải ít nhất bằng số phiếu hiện tại của ứng cử viên có nhiều phiếu nhất (max). Nếu mục tiêu thấp hơn max, ta không thể giảm phiếu của người đang dẫn đầu.

Nếu cả hai điều kiện trên thỏa mãn, đáp án là YES, ngược lại là NO.

Các cách tiếp cận

Cách Mô phỏng đệ quy (Tăng dần mức phiếu)

#include<stdio.h>
int bc(int a[],int n,int k,int max){


for(int i=0;i<n;i++){
    k=k-(max-a[i]);
    a[i]=max;


}
max+=1;

if(k==0){
return 1;
}
else if(k<0){
    return 0;
}
else return bc(a,n,k,max);

}
int main(){
int t;
scanf("%d",&t);
while(t--){
    int n;
int k;


scanf("%d%d",&n,&k);
int a[n];
for(int i=0;i<n;i++){
    scanf("%d",&a[i]);

}
int max= a[0];
for(int i=0;i<n;i++)
if(a[i]>max)
max=a[i];
if(bc(a,n,k,max) ==1)
printf("YES\n");
else printf("NO\n");
}

}

• Time Complexity: O(n) trong thực tế (hoặc O(n * Target) nếu Target lớn)
• Space Complexity: O(1)

Cách tiếp cận này mô phỏng quá trình tăng số phiếu của các ứng cử viên lên một mức chung (level) cho đến khi hết phiếu hoặc đạt được sự cân bằng.

1. Tìm số phiếu hiện tại lớn nhất (max).
2. Tính tổng số phiếu cần để đưa tất cả ứng cử viên lên mức max. Gọi là cost.
3. Nếu k >= cost: Trừ cost khỏi k, tăng tất cả các ứng cử viên lên max. Sau đó tăng max lên 1 và lặp lại.
4. Nếu tại bất kỳ bước nào k bị âm, tức là không thể tăng đều lên mức đó, ta dừng và trả về NO.
5. Nếu k == 0 sau khi tăng đều, trả về YES.

Lưu ý: Solutions sử dụng đệ quy, về cơ bản là lặp lại quy trình cho đến khi k hết hoặc không đủ. Tuy nhiên, cách này có thể chậm nếu k rất lớn.

Cách Tối ưu hóa Toán học (Phân tích điều kiện)

// Online C compiler to run C program online
#include <stdio.h>

int main() {
    int t;
    scanf("%d",&t);
    while(t--){
        int n,k;
    scanf("%d%d",&n,&k);
    int a[n];
    int max=-999,sum=0;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        if(a[i]>max) max=a[i];
        sum+=a[i];
    }
    if(max>(sum+k)/n) printf("NO\n");
    else{
        if((sum+k)%n==0) printf("YES\n");
        else printf("NO\n");
    }

    }

    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là cách tiếp cận hiệu quả nhất, dựa trên việc suy ra các điều kiện tiên quyết.

Giả sử sau khi phân phối phiếu, tất cả đều có số phiếu là X.

1. Tổng số phiếu cuối cùng là sum + k.
2. Vì có n ứng cử viên, nên n * X = sum + k. Do đó, sum + k phải chia hết cho n.
3. Giá trị X (mức phiếu mục tiêu) được tính là (sum + k) / n.
4. Để tất cả ứng cử viên đều có thể đạt được X, ta cần X >= max (vì ta chỉ có thể tăng phiếu, không thể giảm).

Thuật toán:

• Tính tổng sum và max của mảng hiện tại.
• Kiểm tra điều kiện: max <= (sum + k) / n.
• Kiểm tra điều kiện chia hết: (sum + k) % n == 0.
• Nếu cả hai đều đúng, in YES, ngược lại NO.

Cách Phân tích chi tiết (Dựa trên chênh lệch)

#include <stdio.h>
#include <string.h>
#include <math.h>
#define ll long long
int check(int n,int k, int a[]){
  int max_a = a[0];
  int sum_a = 0;
  for(int i=0;i<n;++i){
    if (a[i]>max_a) max_a = a[i];
    sum_a += a[i];
  }
  int temp = k - (max_a * n - sum_a);
  if (temp<0 || temp % n  != 0) return 0;
  return 1;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,k;
        scanf("%d%d",&n,&k);
        int a[n];
        for(int i=0;i<n;++i) scanf("%d",&a[i]);
        if(check(n,k,a)) printf("YES");
        else printf("NO");
        printf("\n");
    }
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Cách tiếp cận này phân tích chi phí cần thiết để san bằng số phiếu.

1. Đầu tiên, cần san bằng mọi người lên mức max hiện tại. Chi phí = n * max - sum. Lượng phiếu còn lại sau bước này: k' = k - (n * max - sum). Nếu k' < 0, tức là không đủ phiếu để san bằng lên max ban đầu -> NO.

2. Sau khi mọi người đều bằng max, ta có k' phiếu còn lại. Để chia đều k' cho n ứng cử viên, k' phải chia hết cho n. Nếu k' % n == 0, YES, ngược lại NO.

Logic này là biến thể của cách tiếp cận Toán học, nhưng đi sâu vào quá trình 'san lấp' trước.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Điều kiện cần và đủ: (Tổng phiếu + k) chia hết cho n VÀ số phiếu mục tiêu (Tổng phiếu + k)/n phải >= số phiếu của ứng cử viên đang dẫn đầu.
• Phép chia lấy dư: Kiểm tra tính chia đều của tổng số phiếu là bước đầu tiên và quan trọng nhất.

Lỗi thường gặp

• Quên kiểm tra điều kiện số phiếu mục tiêu phải lớn hơn hoặc bằng số phiếu hiện tại của người có nhiều phiếu nhất (không thể giảm phiếu).
• Sử dụng số nguyên chia cho số thực trong các ngôn ngữ强类型 (ví dụ: /n thay vì (sum+k)/n) có thể gây sai lệch nếu không cẩn thận, nhưng trong bài này dùng số nguyên là ổn vì điều kiện chia hết.