Detail of message

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

不是要用到10的9次方的内存么？怎么我的会超内存呢？不解，帮忙看一下。（附code）

Posted by RUNSLOWLY at 2009-05-26 20:35:21 on Problem 1009

#include<iostream>
#include<math.h>
using namespace std;
#define size 1000000000 
char map[size];
int n,all;
int zheng,maxr,lef;
int f(int i)
{
	int sum;
	int c=i%n;
	int r=i/n;
	sum=0;
	int mid;
	if(r<maxr-1 || lef==0)
	{
	if(c-1>=0 && r-1>=0)
	{
		mid=abs(map[(r-1)*n+c-1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if((r-1)>=0)
	{
		mid=abs(map[(r-1)*n+c]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if(c+1<n && (r-1)>=0)
	{
		mid=abs(map[(r-1)*n+c+1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if(c+1<n)
	{
		mid=abs(map[(r)*n+c+1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if(c+1<n && (r+1)<maxr)
	{
		mid=abs(map[(r+1)*n+c+1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if((r+1)<maxr)
	{
		mid=abs(map[(r+1)*n+c]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if(c-1>=0 && (r+1)<maxr)
	{
		mid=abs(map[(r+1)*n+c-1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if(c-1>=0)
	{
		mid=abs(map[(r)*n+c-1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	}
	else
	{
	 if(r==maxr-2)
	 {
	//
	if(c-1>=0 && r-1>=0)
	{
		mid=abs(map[(r-1)*n+c-1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if((r-1)>=0)
	{
		mid=abs(map[(r-1)*n+c]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if(c+1<n && (r-1)>=0)
	{
		mid=abs(map[(r-1)*n+c+1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if(c+1<n)
	{
		mid=abs(map[(r)*n+c+1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	//**
	if(c+1<lef)
	{
		mid=abs(map[(r+1)*n+c+1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if(c<lef && c>=0)
	{
		mid=abs(map[(r+1)*n+c]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if(c-1>=0 && c-1<lef)
	{
		mid=abs(map[(r+1)*n+c-1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	//**
	if(c-1>=0)
	{
		mid=abs(map[(r)*n+c-1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	//
	 }
	 else
	 {
		if(c-1>=0 && r-1>=0)
	{
		mid=abs(map[(r-1)*n+c-1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if((r-1)>=0)
	{
		mid=abs(map[(r-1)*n+c]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if(c+1<n && (r-1)>=0)
	{
		mid=abs(map[(r-1)*n+c+1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if(c+1<lef)
	{
		mid=abs(map[(r)*n+c+1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	if(c-1>=0)
	{
		mid=abs(map[(r)*n+c-1]-map[i]);
		if(sum<mid)
			sum=mid;
	}
	 }
	}
	return sum;
}
int main()
{
	int i,j;
	while(1)
	{
		cin>>n;
		if(n<=0)
			break;
		all=0;
		while(1)
		{
			cin>>i>>j;
			if(i<=0 && j<=0)
				break;
			while(j--)
			{
				map[all++]=i;
			}
		}
    maxr=all/n;//求出整数行
	zheng=maxr*n;//形成矩阵的元素个数；
	lef=all-zheng;
		int time,mid;
		time=1;
		j=f(0);
		cout<<n<<endl;
		for(i=1;i<all;i++)
		{
			mid=f(i);
			if(mid==j)
				time++;
			else
			{
				cout<<j<<' '<<time<<endl;
				time=1;
				j=mid;
			}
		}
		cout<<j<<' '<<time<<endl;
	//	cout<<all<<endl;
		cout<<"0 0"<<endl;
	}
	cout<<'0'<<endl;
	return 0;
}

Followed by:

这个题目就是考验你是否能想到节约内存的方法 (0) 3xian 2009-05-26 22:49:10

Post your reply here:

User ID:
Password:
Title:

Content:

> #include<iostream>
> #include<math.h>
> using namespace std;
> #define size 1000000000 
> char map[size];
> int n,all;
> int zheng,maxr,lef;
> int f(int i)
> {
> 	int sum;
> 	int c=i%n;
> 	int r=i/n;
> 	sum=0;
> 	int mid;
> 	if(r<maxr-1 || lef==0)
> 	{
> 	if(c-1>=0 && r-1>=0)
> 	{
> 		mid=abs(map[(r-1)*n+c-1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if((r-1)>=0)
> 	{
> 		mid=abs(map[(r-1)*n+c]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if(c+1<n && (r-1)>=0)
> 	{
> 		mid=abs(map[(r-1)*n+c+1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if(c+1<n)
> 	{
> 		mid=abs(map[(r)*n+c+1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if(c+1<n && (r+1)<maxr)
> 	{
> 		mid=abs(map[(r+1)*n+c+1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if((r+1)<maxr)
> 	{
> 		mid=abs(map[(r+1)*n+c]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if(c-1>=0 && (r+1)<maxr)
> 	{
> 		mid=abs(map[(r+1)*n+c-1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if(c-1>=0)
> 	{
> 		mid=abs(map[(r)*n+c-1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	}
> 	else
> 	{
> 	 if(r==maxr-2)
> 	 {
> 	//
> 	if(c-1>=0 && r-1>=0)
> 	{
> 		mid=abs(map[(r-1)*n+c-1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if((r-1)>=0)
> 	{
> 		mid=abs(map[(r-1)*n+c]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if(c+1<n && (r-1)>=0)
> 	{
> 		mid=abs(map[(r-1)*n+c+1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if(c+1<n)
> 	{
> 		mid=abs(map[(r)*n+c+1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	//**
> 	if(c+1<lef)
> 	{
> 		mid=abs(map[(r+1)*n+c+1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if(c<lef && c>=0)
> 	{
> 		mid=abs(map[(r+1)*n+c]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if(c-1>=0 && c-1<lef)
> 	{
> 		mid=abs(map[(r+1)*n+c-1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	//**
> 	if(c-1>=0)
> 	{
> 		mid=abs(map[(r)*n+c-1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	//
> 	 }
> 	 else
> 	 {
> 		if(c-1>=0 && r-1>=0)
> 	{
> 		mid=abs(map[(r-1)*n+c-1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if((r-1)>=0)
> 	{
> 		mid=abs(map[(r-1)*n+c]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if(c+1<n && (r-1)>=0)
> 	{
> 		mid=abs(map[(r-1)*n+c+1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if(c+1<lef)
> 	{
> 		mid=abs(map[(r)*n+c+1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	if(c-1>=0)
> 	{
> 		mid=abs(map[(r)*n+c-1]-map[i]);
> 		if(sum<mid)
> 			sum=mid;
> 	}
> 	 }
> 	}
> 	return sum;
> }
> int main()
> {
> 	int i,j;
> 	while(1)
> 	{
> 		cin>>n;
> 		if(n<=0)
> 			break;
> 		all=0;
> 		while(1)
> 		{
> 			cin>>i>>j;
> 			if(i<=0 && j<=0)
> 				break;
> 			while(j--)
> 			{
> 				map[all++]=i;
> 			}
> 		}
>     maxr=all/n;//求出整数行
> 	zheng=maxr*n;//形成矩阵的元素个数；
> 	lef=all-zheng;
> 		int time,mid;
> 		time=1;
> 		j=f(0);
> 		cout<<n<<endl;
> 		for(i=1;i<all;i++)
> 		{
> 			mid=f(i);
> 			if(mid==j)
> 				time++;
> 			else
> 			{
> 				cout<<j<<' '<<time<<endl;
> 				time=1;
> 				j=mid;
> 			}
> 		}
> 		cout<<j<<' '<<time<<endl;
> 	//	cout<<all<<endl;
> 		cout<<"0 0"<<endl;
> 	}
> 	cout<<'0'<<endl;
> 	return 0;
> }
>

Home Page Go Back To top