이분법 최대 치 최소 화 문제 해결
n 개의 정 수 를 포함 하 는 서열 을 m 개의 연속 적 인 하위 서열 로 나누다.i 번 째 서열 의 각 수의 합 을 S (i) 로 설정 하고 모든 S (i) 의 최대 치 를 구 하 는 것 이 가장 작은 것 은 얼마 입 니까?
예 를 들 어 서열 1, 2, 3, 5, 4 를 3 개의 서열 로 나 누 는 가장 좋 은 방안 은 1, 2, 3 | 25 이다. 그 중에서 S (1), S (2), S (3) 는 각각 6, 7, 4 이 고 최대 치 는 7 이다.
12 | 32 | 54 로 나 누 면 최대 치 는 9 로 가장 작은 것 이 아니다.
알고리즘 사고
최대 치 를 최소 화 하 는 문 제 를 해결 하려 면 기본 적 인 사 고 는 임의의 범위 (배열 의 최대 치 를 배열 의 모든 요소 의 합 으로 입력 하 는 것) 를 선택 한 다음 에 이 범위 에서 이분법 을 하고 매번 범위 의 중간 치 mid 를 최소 치 로 한 다음 에 mid 값 에서 배열 이 m 부분 으로 나 눌 수 있 는 지 판단 하 는 것 이다.
코드 는 다음 과 같 습 니 다:
#include <stdio.h>
int n,m;
bool judge(const int *a,int key)
{
int sum=0;
int count=0;
for(int i=0;i<n;i++)
{
sum += a[i];
if(sum>key)
{
sum=a[i];
count++;
}
}
if((count+1)<=m)
return 1;
return 0;
}
void binary(const int *a,int left,int right)
{
while(left<right)
{
int mid=(left+right)/2;;/// left+((right-left)>>1)
if(judge(a,mid))
{
right = mid;
}
else
{
left = mid+1;
}
}
printf("%d
",left); // ,right %d
}
int main()
{
int t;
int a[505];
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
int left=0;
int right=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
right += a[i];
if(a[i]>left)
{
left = a[i];
}
}
binary(a,left,right);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
