oil_pipe.cpp

石油管道问题

#include<stdio.h>
#include <math.h>
#include <stdlib.h>
int partition(int a[],int p,int r)//快速排序的划分函数
{
     int i,j,x,temp;
     i=p;
     j=r+1;
     x=a[p];
     while (1)
     {
         while (a[++i]<x);
         while(a[--j]>x);
         if (i>=j)break;
         temp=a[i];
         a[i]=a[j];
         a[j]=temp;
     }
     a[p]=a[j];
     a[j]=x;
     return j;
}
int randpartition(int a[],int p,int r)//随机划分函数
{
     int i;
     i=p+rand()%(r-p+1);//生产随机数
     int temp;
     temp=a[i];
     a[i]=a[p];
     a[p]=temp;
     return partition(a,p,r);//调用划分函数
}
int Median (int a[],int p,int r,int k)//查找中位数函数
{
     if (p==r)//递归结束，找到中位数
     {
         return a[p];
     }
     int i,j;
     i=randpartition(a,p,r);//划分
     j=i-p+1;
     if (k==j)//递归结束，找到中位数
         return a[i];
     if (k<j)
     {
         return Median (a,p,i-1,k);//递归调用，在前面部分查找中位数
     }
     else
         return Median (a,i+1,r,k-j);//递归调用，在后面部分查找中位数
}
void main()
{
    int i,n,mid,min=0,arrx[20],arry[20];
	FILE *fp,*fp1,*fp2;
	printf("请输入油井的个数n:\n");
	scanf("%d",&n);
	printf("请输入各油井的位置(x,y):\n");
	for(i=0;i<n;i++)
	{
		scanf("%d",&arrx[i]);
		scanf("%d",&arry[i]);
	}
	fp=fopen("input.txt","w");
	fprintf(fp,"%d\n",n);
    for(i=0;i<n;i++)
		fprintf(fp,"%d %d\n",arrx[i],arry[i]);
	fp1=fopen("input.txt","r");
	fprintf(fp1,"%d\n",n);
    for(i=0;i<n;i++)
		fprintf(fp1,"%d %d\n",arrx[i],arry[i]);
	mid= Median (arry,0,n-1,(n+1)/2);
	for(i=0;i<n;i++)
	{
		min+=fabs(arry[i]-mid);
	}
	fp2=fopen("output.txt","w");
    fprintf(fp2,"%d\n",min);
	printf("%d\n",min);
}