5410 : C11 - 선거 (Election)
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
오늘 KYOPRO 국에서는 총선이 치러졌습니다. $N$ 개의 정당이 입후보했고, $i$ 번째 정당은 $A_i$ 표를 얻었습니다.
비례대표제에 따라 $K$ 석의 의석을 배분할 때, 각 정당이 획득하게 되는 의석수를 구하는 프로그램을 작성하십시오.
단, 비례대표제는 **"득표수 ÷ (현재 획득 의석수 + 1)"**의 몫이 가장 큰 정당에게 의석을 하나씩 차례대로 할당하는 동트(D'Hondt) 방식을 적용합니다.
[제약 조건]
• $1 \le N \le 100{,}000$
• $1 \le K \le 10^9$
• $1 \le A_i \le 10^9$
• 몫이 정확히 같아 동석 배분이 모호해지는 경우는 주어지지 않습니다.
• 입력되는 모든 값은 정수입니다.
비례대표제에 따라 $K$ 석의 의석을 배분할 때, 각 정당이 획득하게 되는 의석수를 구하는 프로그램을 작성하십시오.
단, 비례대표제는 **"득표수 ÷ (현재 획득 의석수 + 1)"**의 몫이 가장 큰 정당에게 의석을 하나씩 차례대로 할당하는 동트(D'Hondt) 방식을 적용합니다.
[제약 조건]
• $1 \le N \le 100{,}000$
• $1 \le K \le 10^9$
• $1 \le A_i \le 10^9$
• 몫이 정확히 같아 동석 배분이 모호해지는 경우는 주어지지 않습니다.
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 정수 $N$ 과 $K$ 가 공백으로 구분되어 주어집니다.
둘째 줄에 각 정당의 득표수 $A_1, A_2, \dots, A_N$ 이 공백으로 구분되어 주어집니다.
둘째 줄에 각 정당의 득표수 $A_1, A_2, \dots, A_N$ 이 공백으로 구분되어 주어집니다.
출력 설명
각 정당이 획득하는 의석수를 $1$ 번 정당부터 순서대로 공백으로 구분하여 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 10
1000000 700000 300000 180000
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3 1 1도움
동트 방식에 따라 의석을 순차적으로 배분하면 1번 정당 5석, 2번 정당 3석, 3번 정당 1석, 4번 정당 1석이 됩니다.