| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
超出内存限制 求大神帮忙看一看怎么样不超出内存限制#include<stdio.h>
#include<math.h>
int Part(int a[],int p,int r);
void Quick_sort(int a[],int p,int r);
int Rand_slect(int a[],int p,int r,int k);
int main(){
int n,x[10001],y[10001];
int i,j,term;
long int sum=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d",&x[i],&y[i]);
}
term=Rand_slect(y,1,n,(n+1)/2);
for(i=1;i<=n;i++){
sum=sum+abs(y[i]-term);
}
Quick_sort(x,1,n);
for(i=1,j=0;i<=n;i++,j++){
x[i]=x[i]-j;
}
term=Rand_slect(x,1,n,(1+n)/2);
for(j=1;j<=n;j++){
sum+=abs(x[j]-term);
}
printf("%ld",sum);
return 0;
}
int Part(int a[],int p,int r){
int term;
term=a[p];
while(p<r){
while(p<r&&term<a[r]) r--;
a[p]=a[r];
while(p<r&&a[p]<=term) p++;
a[r]=a[p];
}
a[p]=term;
return p;
}
void Quick_sort(int a[],int p,int r){
int k;
k=Part(a,p,r);
if(p>=r) return;
Quick_sort(a,p,k-1);
Quick_sort(a,k+1,r);
}
int Rand_slect(int a[],int p,int r,int k){
int i,j;
if(p-1==r) return a[p];
i=Part(a,p,r);
j=i-p+1;
if(j==k) return a[i];
else if(j<k) Rand_slect(a,p,i,k);
if(j>k) Rand_slect(a,i+1,r,k-j);
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator