首页 > ACM题库 > HDU-杭电 > HDU 4007-Dave-排序-[解题报告]HOJ
2015
04-14

HDU 4007-Dave-排序-[解题报告]HOJ

Dave

问题描述 :

Recently, Dave is boring, so he often walks around. He finds that some places are too crowded, for example, the ground. He couldn’t help to think of the disasters happening recently. Crowded place is not safe. He knows there are N (1<=N<=1000) people on the ground. Now he wants to know how many people will be in a square with the length of R (1<=R<=1000000000). (Including boundary).

输入:

The input contains several cases. For each case there are two positive integers N and R, and then N lines follow. Each gives the (x, y) (1<=x, y<=1000000000) coordinates of people.

输出:

The input contains several cases. For each case there are two positive integers N and R, and then N lines follow. Each gives the (x, y) (1<=x, y<=1000000000) coordinates of people.

样例输入:

3 2
1 1
2 2
3 3

样例输出:

3

Hint
If two people stand in one place, they are embracing.

题意:给你n个点(n<=1000),然后给你一个正方形,问这个正方形最多能覆盖多少个点。

一般思路都是将正方形先x方向移然后再向y移求最大,显然是需要排序的,方便统计。那么会不会tle呢?两个for,n*n 可以满足。没什么陷阱,果断1y。。。最近状态不错。。。

Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author
4602505 2011-09-14 21:37:34 Accepted 4007 109MS 284K 1088 B G++ xym2010
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF=1000100000;
struct node
{
	int x,y;
}n[1010];
bool cmp(node a,node b)
{
	return a.x<b.x;
}
int main()
{
	int p,r,xmax,xmin,ymax,ymin,y[1010];
	while(scanf("%d%d",&p,&r)!=EOF)
	{
		ymax=xmax=-INF;ymin=xmin=INF;
		for(int i=0;i<p;i++)
		{
			scanf("%d%d",&n[i].x,&n[i].y);
			if(ymax<n[i].y)ymax=n[i].y;
			if(ymin>n[i].y)ymin=n[i].y;
			if(xmax<n[i].x)xmax=n[i].x;
			if(xmin>n[i].x)xmin=n[i].x;
		}
		if((ymax-ymin<=r)&&(xmax-xmin<=r))
		{
			printf("%d\n",p);
			continue;
		}
		else
		{
			sort(n,n+p,cmp);
			int ans=0;
			for(int i=0;i<p;i++)
			{
				int k=0;
				for(int j=i;n[j].x<=n[i].x+r&&j<p;j++)
				{
					y[k++]=n[j].y;
				}
				sort(y,y+k);
				int count=0,tem=0;
				for(int j=0;j<k&&tem<k;j++)
				{
					while(y[tem]-y[j]<=r&&tem<k)tem++;
					if(count<tem-j)count=tem-j;
				}
				if(ans<count)ans=count;
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/xymscau/article/details/6776182


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.