- 浏览: 32683 次
最新评论
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define MAX 100000
void ps(int a[],int low,int high) //快速排序
{
int key,i,j;
i=low;
j=high;
key=a[low];
if(low>high) return;
while(i<j)
{
while(key<=a[j] && i<j )
j--;
a[i]=a[j];
while(i<j && key>=a[i])
i++;
if(low<high)
a[j]=a[i];
}
a[i]=key;
ps(a,low,j-1);
ps(a,i+1,high);
}
int main()
{
int a[MAX],b[MAX];
int n,i,j,sum,mid;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n*2;i++)
{
scanf("%d",&a[i]);
}
for(i=1,j=0;i<n*2;j++,i=i+2)
{
b[j]=a[i];
}
ps(b,0,n-1);
sum = 0;
mid = b[(n-1) / 2];
for(i = 0; i < n; i++)
sum += abs(b[i] - mid); //找出中位数
printf("%d\n",sum);
}
return 0;
}
#include <math.h>
#include <stdlib.h>
#define MAX 100000
void ps(int a[],int low,int high) //快速排序
{
int key,i,j;
i=low;
j=high;
key=a[low];
if(low>high) return;
while(i<j)
{
while(key<=a[j] && i<j )
j--;
a[i]=a[j];
while(i<j && key>=a[i])
i++;
if(low<high)
a[j]=a[i];
}
a[i]=key;
ps(a,low,j-1);
ps(a,i+1,high);
}
int main()
{
int a[MAX],b[MAX];
int n,i,j,sum,mid;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n*2;i++)
{
scanf("%d",&a[i]);
}
for(i=1,j=0;i<n*2;j++,i=i+2)
{
b[j]=a[i];
}
ps(b,0,n-1);
sum = 0;
mid = b[(n-1) / 2];
for(i = 0; i < n; i++)
sum += abs(b[i] - mid); //找出中位数
printf("%d\n",sum);
}
return 0;
}
发表评论
-
最大子段和
2012-01-05 13:59 779给出N个数字, 计算出最大的子段和。 Input 第一行给 ... -
最长不下降子序列长度
2012-01-05 13:55 1309对于序列(1, 7, 3, 5, 9, 4,,有它的一些不下降 ... -
求两字符串匹配的最长子序列
2012-01-05 13:52 1016如果两种特征序列的公共子序列越长表示越接近,现在请你帮助计算出 ... -
编辑距离问题
2012-01-05 13:48 658#include<iostream> #incl ... -
Kruskal最小生成树
2011-12-08 14:26 699#include<iostream> #inclu ... -
prime
2011-12-01 20:09 612#include<iostream> using ... -
哈弗曼编码
2011-11-28 10:43 1#include<iostream> #defi ... -
哈弗曼编码
2011-11-28 10:42 520#include<iostream> #defi ... -
#贪心算法(零件加工)
2011-10-27 13:25 981#include<stdio.h> #includ ... -
众数问题
2011-10-20 14:57 789#include <stdio.h> #inclu ... -
幂的精确求值
2011-09-22 15:07 461#include<iostream> using ... -
大数加法
2011-09-22 12:56 606#include<iostream> #incl ... -
三姐妹之出题
2011-09-15 14:15 663#include<iostream> #incl ... -
最大子段和问题(分治)(##)
2011-09-08 21:31 665#include<stdio.h> #defin ... -
最大子段和问题(O(N^2))
2011-09-08 15:04 610#include<stdio.h> int a[ ... -
最大子段和问题(O(N^3))
2011-09-08 14:45 476#include<stdio.h> int a[ ...
相关推荐
输油管道问题,在VC6.0中实现,算法参考《计算机算法设计与分析》(王晓东)。分治算法RandomizedSelect
输油管道问题:可能有点小问题,自己修改一下,只提供参考。
输油管道问题,程序设计,程序源码……………… 内含具体设计方法
输油管道问题 Time Limit:2000MS Memory Limit:65536K Total Submit:392 Accepted:242 Description 问题描述: 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都...
输油管道问题 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标(东西向)...
本个资源还可以!可能在某环境下不能运行!总之,还可以的!
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北...
改进的可以在C语言环境下实现的算法,可能还有许多需要改进的地方。
#include "stdio.h" #include "stdlib.h" #include "math.h" main() {int i,j,sum=0,n,mode=0,temp,z; scanf("%d",&n); int a[n+1]; for(i=1;i;i++) scanf("%d%d",&z,&a[i]); for(i=1;i;... }
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n 口油井的位置,即它们的x 坐标(东西向)和y 坐标...
讲述经典的输油管道问题,分析的比较具体,很值得一看
输油管道问题排序
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x坐标(东西向)和y坐标(南北向...
某石油公司计划建造一条由南向北的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道眼最短路径(或东或西)与主管道相连。如果给定n口油井的位置,即它们的x坐标(东西向)和y坐标(南北...