nums라고 하는 정수 배열과 임계값인 정수 k가 있다고 가정하고 양의 정수 제수를 선택하고 모든 배열을 그것으로 나누고 나누기 결과를 합산합니다. 위에서 언급한 결과가 임계값 k보다 작거나 같도록 가장 작은 제수를 찾아야 합니다. 예를 들어 - nums =[1,2,5,9]이고 k =6이면 출력은 5가 됩니다. 제수가 1일 때 (1+2+5+9) =17로 합을 얻을 수 있습니다. 제수가 4이면 합 7을 (1+1+2+3)으로 얻을 수 있고, 제수가 5이면 합은 (1+1+1+2) =5가 됩니다.
반드시 답이 있을 것입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- check라는 메서드 하나를 정의합니다. x, 배열 번호 및 k와 같은 세 개의 매개변수를 사용합니다. 다음과 같습니다. -
- 합계 :=0
- 0에서 숫자 크기 – 1까지 범위에 있는 i의 경우
- sum :=sum + nums[i] / x의 상한값
- 합이 <=k이면 true, 그렇지 않으면 false를 반환
- 실제 방법은 아래와 같습니다 -
- 낮음 :=1 및 높음 :=inf로 설정
- 낮은 동안 <높음
- 중간 :=낮음 + (높음 – 낮음)/2
- check(mid, nums, k)이면 high :=mid, 그렇지 않으면 low :=mid + 1
- 높은 수익
- 더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(int x, vector <int> &nums, int th){
int sum = 0;
for(int i = 0; i < nums.size(); i++){
sum += ceil((double)nums[i]/(double)x);
}
return sum<=th;
}
int smallestDivisor(vector<int>& nums, int th) {
int low = 1;
int high = 1e7;
while(low < high){
int mid = low + (high - low)/2;
if(ok(mid, nums, th)){
high = mid;
}else low = mid + 1;
}
return high;
}
};
main(){
vector<int> v = {1,2,5,9};
Solution ob;
cout << (ob.smallestDivisor(v, 6));
} 입력
[1,2,5,9] 6
출력
5