cpp1.cpp

算法课上的分治算法

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define N 500000
typedef struct node
{
	float min;
	float max;
}NODE;
  
float a[N];
NODE minmax(long low,long high)
{
	NODE result,result1,result2;
	float x,y;
	long mid;
	if((high-low)==1)
		if(a[low]<a[high])
		{
			result.min=a[low];
			result.max=a[high];
		   	return result;
		}
		else 
		{
			result.min=a[high];
			result.max=a[low];
			return result;
		}
		mid=(low+high)/2;
		result1=minmax(low,mid);
		result2=minmax(mid,high);
		if(result1.min<=result2.min)
			x=result1.min;
		else x=result2.min;
		if(result1.max>=result2.max)
			y=result1.max;
		else y=result2.max;
		result.min=x;
		result.max=y;
		return result;
}
int main()
{
	long i;
	long n;
	NODE r1,r2;
for(scanf("%ld",&n);n>0;scanf("%ld",&n))
{
	for(i=1;i<=n;i++)
		scanf("%f",&a[i]);
	   r1=minmax(1,n);
		for(i=1;a[i]!=r1.max;i++);
        a[i]=r1.min;
		r2=minmax(1,n);
		printf("%.0f\n",r2.max);
}
	return 0;
}