ZOJ2499  题目一样 就是数据范围变大一点
我除了把数组范围调到相应值以外  其它都没动
270ms过了
而且ZOJ的限制时间是2S POJ是5S
POJ你这不是坑爹么 我现在在POJ三次超时  还不知道怎么办
代码贴出来 跪求大牛赐教

#include<iostream>
#include<algorithm>
using namespace std;

struct node{
	int x;
	int y;
}s[200010];//ZOJ的数据范围是20W
bool cmpa(node a,node b)
{
	if(a.x!=b.x)
		return a.x<b.x;
	else
		return a.y<b.y;
}
bool cmpb(node a,node b)
{
	if(a.y!=b.y)
		return a.y<b.y;
	else
		return a.x<b.x;
}
int coua(int k,int n)
{
	int sum=0,i;
	for(i=1;i<=k;i++)
	{
		if(s[i].x!=s[i-1].x)
		{
			sum+=(s[i].x-s[i-1].x-1);
			if(s[i].y>2)
				sum++;
			if(n-s[i-1].y>=2)
				sum++;
		}
		else
		{
			if(s[i].y-s[i-1].y>2)
				sum++;
		}
	}
	return sum;
}
int coub(int k,int m)
{
	int sum=0,i;
	for(i=1;i<=k;i++)
	{
		if(s[i].y!=s[i-1].y)
		{
			sum+=(s[i].y-s[i-1].y-1);
			if(s[i].x>2)
				sum++;
			if(m-s[i-1].x>=2)
				sum++;
		}
		else
		{
			if(s[i].x-s[i-1].x>2)
				sum++;
		}
	}
	return sum;
}
int main()
{
	int t,m,n,k;
	int i,sum;
	cin>>t;
	while(t--)
	{
		cin>>m>>n>>k;
		for(i=1;i<=k;i++)
			cin>>s[i].x>>s[i].y;
		sum=0;
		if(n>=2)
		{
			s[0].x=1;
			s[0].y=0;
			s[k+1].x=m+1;
			s[k+1].y=0;
			sort(s+1,s+k+1,cmpa);
			sum+=coua(k+1,n);
		}
		if(m>=2)
		{
			s[0].x=0;
			s[0].y=1;
			s[k+1].x=0;
			s[k+1].y=n+1;
			sort(s+1,s+k+1,cmpb);
			sum+=coub(k+1,m);
		}
		cout<<sum<<endl;

	}
	return 0;
}
/*

1
5 5 6
1 5
2 3
2 4
4 2 
4 3
5 1





*/

• 自己站沙发 AC啦 (74) 2407_chensongkui 2012-02-01 21:16:43
  • Re:自己站沙发 AC啦 (112) jackchongs 2013-05-12 12:28:39