최대 치 최소 화 문제 - 분할
4315 단어 알고리즘
12 | 32 | 54 로 나 누 면 최대 치 는 9 로 가장 작은 것 이 아니다.
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 로 가장 작은 것 이 아니다.
분석: 이 문 제 는 이분 의 사상 으로 풀 수 있다.한 줄 의 숫자 에서 가장 작은 값 부터 특정한 값 까지 모두 성립 될 수 있 고 그 후에 도 성립 될 수 없다.반대로 2 분 의 사상 을 사용 할 수 있다.
#include <stdio.h>
#define max 1000
int totalnum, sequencenum;
int judge(int *array, int test);
int value(int *array, int low, int high);
int main() {
scanf("%d%d", &totalnum, &sequencenum);
int maxn, minn = max;
int input[max];
for (int i = 0; i < totalnum; i++) {
scanf("%d", &input[i]);
maxn += input[i];
if (minn > input[i]) {
minn = input[i];
}
}
int answer = value(input, minn, maxn);
printf("%d
", answer);
}
int judge(int *array, int test) {
int sum = 0;
int sequence = 0;
for (int i = 0; i < totalnum; i++) {
sum += array[i];
if (sum > test) {
sum = array[i];
sequence++;
}
}
if (sequence >= sequencenum) {
return 0;
} else {
return 1;
}
}
int value(int *array, int low, int high) {
if (low > high) {
return high + 1;
}
int mid = (low + high) / 2;
if (judge(array, mid) == 1) {
return value(array, low, mid - 1);
} else {
return value(array, mid + 1, high);
}
return 0;
}
이분 알고리즘 을 사용 하 는 데 걸 리 는 시간 은 o (nlog 2 (n) 이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
