컴퓨터 알고리즘 설계 및 분석 1 - 5 최대 간극 문제

최대 간극 문제
                              
                              
질문 설명:
                              
                              
        n 개의 실수 x1, x2,..., xn 을 지정 하고 이 n 개의 실수 가 실제 축 에 인접 한 2 개의 수 간 의 최대 차 이 를 구하 고 선형 시간 알고리즘 을 설계 해 야 합 니 다.
                              
이 문 제 를 보고 첫 번 째 느낌 으로 정렬 하고 싶 지만 O (nlogn) 는 O (n) 보다 현저히 크다.
마지막 으로 이 문 제 를 풀 때 비둘기 우리 의 원 리 를 사 용 했 는데 n - 1 개의 물건 을 n 개의 서랍 에 넣 으 면 적어도 한 개의 서랍 이 비어 있다 는 것 이다.
본 문제 에 서 는 총 n 개의 점 이 있 는데 이 선 을 n - 1 단 으로 나 누고 구간 길 이 를 총 길이 로 n - 1 로 나 누 어 좌우 점 을 제외 한 n - 2 개의 점 을 이 n - 1 구간 에 두 는 것 이다.
적어도 한 구간 은 비어 있 고, 가장 큰 인접 간극 은 좌우 구간 중간 에 빈 상태 에서 발생 하 며, 한 구간 이 아 닌 다음 구간 의 왼쪽 경 계 를 찾 아 이전 구간 의 오른쪽 경계 최대 치 를 빼 면 된다.

#include
using namespace std;
#define inf 1<<30
#define m 10000
int n;
double num[m],maxn=-inf,minn=inf;
double maxx[m],mixx[m];
double left;
int book[m];
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf",&num[i]);
		maxn=maxn>num[i]?maxn:num[i];
		minn=minnnum[i])
			mixx[bucket]=num[i];
	}
	double res=0,left=maxx[1];
	for(int i=2;i<=n-1;i++)
	{
		if(book[i]){
			double tep=mixx[i]-left;
			left=maxx[i];
			if(res

 
최근 학습 에서 가장 짧 은 인접 거 리 를 찾 는 것 을 보 았 습 니 다. 원래 이렇게 O (n) 가 하려 고 했 는데 이 문제 와 달리 가장 짧 은 거 리 를 찾 는 것 은 N 개의 점 을 N - 1 구간 에 두 고 적어도 한 구간 안에 두 개의 점 이 있 습 니 다. 각 구간 의 가장 오른쪽 에 있 는 왼쪽 점 과 가장 왼쪽 에 있 는 오른쪽 점 을 업데이트 하 는 것 입 니 다. 하지만 이렇게 할 수 없습니다.한 점 을 업데이트 하 는 것 은 다음 업데이트 에 영향 을 미 칠 수 있 기 때문에 정렬 을 해 야 합 니 다. 가장 짧 은 인접 거 리 를 찾 아 도 O (nlogn) 가 필요 합 니 다. 위 에서 가장 먼 거 리 를 찾 으 면 이렇게 할 수 있 는 것 은 반드시 두 구간 에서 점 을 찾 아야 하기 때 문 입 니 다. 각 구간 의 최대 와 최소 만 찾 으 면 두 구간 에서 반드시 인접 해 있 고 가장 가 까 운 것 을 찾 으 면 이 점 을 할 수 없습니다.한 번 의 스 캔 업 데 이 트 를 통 해 좌우 점 이 인접 하고 거리 가 가장 짧다 는 것 을 보장 할 수 없습니다.