No.2792: 보석함
보석 공장에서 보석 상자를 유치원에 기증했습니다. 각 보석은 M개의 다른 색상 중 하나입니다. 원장은 모든 보석을 N명의 학생들에게 나눠주려고 합니다. 이 시점에서 받은 보석은 없습니다.
www.acmicpc.net
보석 공장에서 보석 상자를 유치원에 기증했습니다. 각 보석은 M개의 다른 색상 중 하나입니다. 원장은 모든 보석을 N명의 학생들에게 나눠주려고 합니다. 현재 일부 학생은 보석으로 석방되지 않을 수 있습니다. 그러나 학생은 항상 같은 색상의 보석만 가져갑니다.
한 아이가 보석을 너무 많이 가져가면 다른 아이들이 질투합니다. 감독은 이 부러움을 가장 많은 보석을 가져간 학생이 소유한 보석의 수로 정량화했습니다. 감독은 질투를 최소화하기 위해 보석을 나눠주려 했다.
상자에 4개의 빨간색 보석(RRRR)과 7개의 파란색 보석(BBBBBBB)이 있다고 가정하고 이 보석을 5명의 어린이에게 나눕니다. Jewel을 RR, RR, BB, BB, BBB로 나누면 Jealousy는 3이 되며 이보다 작을 수 없습니다.
학생 수와 상자 안의 보석에 대한 정보가 주어지면 질투를 최소화하는 방식으로 보석을 분배하는 방법을 계산하는 프로그램을 작성하십시오.
입력하다
첫 번째 줄은 N 자식의 수와 M 색상의 수를 제공합니다. (1≤N≤109, 1≤M≤300,000, M≤N)
다음 M 행에는 간격 (1, 109)에 포함된 양의 정수가 제공됩니다. K 행에 주어진 숫자는 K 색상의 보석 수입니다.
인쇄
envy의 최소값을 첫 번째 줄에 인쇄합니다.
예시 입력 1
5 2
7
4
예제 출력 1
3
해결하다
- 배열을 정렬한 후 기준점을 0으로 최소값(왼쪽)으로 설정하고 배열에서 가장 큰 숫자를 최대값(오른쪽)으로 설정하여 매개변수를 사용하여 검색합니다. (부러움 지표는 가장 많은 보석의 수이므로 가능한 최대의 부러움입니다.)
- 중간에 따라 보석을 나누면 나눌 수 있는 최대 인원(카운트)이 나오므로, 카운트가 나누어지는 인원보다 크면 왼쪽을 늘리고, 적으면 왼쪽을 늘리거나, 숫자와 같으면 검색 범위를 좁히면서 검색 범위를 좁힙니다.죄송합니다
코드
const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
const (n, m) = input.shift().split(' ').map(el=>+el);
const arr = input.map(el=>+el);
arr.sort((a,b)=>a-b);
let left = 0;
let right = arr(m-1);
let mid = Math.floor((left + right)/2);
while(left < right) {
let count = 0;
for(let i = 0 ; i < m; i++) {
if(arr(i)%mid===0) count += Math.floor(arr(i)/mid);
else count += Math.floor(arr(i)/mid) + 1;
}
if(count > n) {
left = mid+1;
}
else {
right = mid;
}
mid = Math.floor((left+right)/2);
}
console.log(mid);