一 日 四 问
查看原帖
一 日 四 问
282080
RefreshinglyNaive楼主2020/5/3 19:58

小C想请喜欢的女生看电影,结果惨遭婉拒。小C很伤心。他在某一天晚上做了一个梦,在梦里他喜欢的女生答应小C一起去看电影。 小C十分兴奋地去买电影票,但是有个要求,希望能买到离正中间位置的距离尽可能近的连续的两个位置。 假设电影院有n排m列,保证n是奇数,m是偶数。正中间的两个位置的坐标即为((n+1)/2,m/2)和((n+1)/2,m/2+1) 这里的距离定义为对应位置的横坐标之差的绝对值加上纵坐标之差的绝对值的和。假设最终选择位置是(x2,y2),(x2,y2+1),正中间位置为(x1,y1),(x1,y1+1),则两个位置距离可以描述为:∣x2−x1∣+∣y2−y1∣ 现在已知有k个位置已经被人预订了,小C想找到连续的两个座位(注意:这里的连续必须是同排相邻列)满足上述要求,请你帮忙找出这两个位置并输出。

Input 第一行一个整数 T 表示数据组数。T <= 20 对于每一组数据: 第 1 行三个整数 n,m,k,分别表示电影院的排数、列数以及已经被预订的位置个数。 接下来 k 行,每行给出两个整数 u,v,表示 (u,v)这个位置已经被其他人预订。 数据范围保证:n,m≤1000,k≤n∗m

Output 对于每组数据,输出两个坐标,表示小C找到的符合条件的连续的两个座位的位置,中间用空格隔开,占一行。 如果找不到符合条件的连续的两个座位,则输出"-1"。 如果有多种答案,优先取排数尽可能小的。如果排数相同,则优先取列数尽可能小的。

#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
int g[maxn][maxn],n,m,flag;
int mx,my,minans,minx,miny;
int main()
{
	ios::sync_with_stdio(false);
	int t,i,k,x,y,j,ans;
	cin>>t;
	while(t--)
	{
		cin>>n>>m>>k;
		memset(g,0,sizeof(g));
		for(i=1;i<=k;i++) 
		{
			cin>>x>>y;
			g[x][y]=1;
		}
		mx=(n+1)/2; my=m/2; 
		minans=0xfffff; minx=0; miny=0;
		flag=0;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m-1;j++)
			{
				ans=abs(i-mx)+abs(j-my);
				//if(ans>minans) break;
				if(g[i][j]==0&&g[i][j+1]==0)
				{
					if(ans<minans)
					{
						minans=ans;
						minx=i; miny=j;
						flag=1;
					}
				}
			}
		}
		if(!flag) cout<<"-1\n";
		else printf("(%d,%d) ( %d,%d)\n",minx,miny,minx,miny+1);
	}
	return 0;
} 

求为什么错了(第二次)

2020/5/3 19:58
加载中...