Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

超出内存限制 求大神帮忙看一看怎么样不超出内存限制

Posted by tsb123 at 2021-09-15 21:45:20 on Problem 1723
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator