【水数组】#29 A. Spit Problem

87 阅读 0 评论 58 点赞

我是靠谱客的博主热情苗条，这篇文章主要介绍【水数组】#29 A. Spit Problem，现在分享给大家，希望可以做个参考。

In a Berland's zoo there is an enclosure with camels. It is known that camels like to spit. Bob watched these interesting animals for the whole day and registered in his notepad where each animal spitted. Now he wants to know if in the zoo there are two camels, which spitted at each other. Help him to solve this task.

The trajectory of a camel's spit is an arc, i.e. if the camel in position x spits d meters right, he can hit only the camel in position x + d, if such a camel exists.

Input

The first line contains integer n (1 ≤ n ≤ 100) — the amount of camels in the zoo. Each of the following n lines contains two integers x_iand d_i ( - 10⁴ ≤ x_i ≤ 10⁴, 1 ≤ |d_i| ≤ 2·10⁴) — records in Bob's notepad. x_i is a position of the i-th camel, and d_i is a distance at which the i-th camel spitted. Positive values of d_i correspond to the spits right, negative values correspond to the spits left. No two camels may stand in the same position.

Output

If there are two camels, which spitted at each other, output YES. Otherwise, output NO.

        Sample test(s) 
      

          input 
        
复制代码2
0 1
1 -1
2
0 1
1 -1

          output 
        
复制代码YES
YES

          input 
        
复制代码3
0 1
1 1
2 -2
3
0 1
1 1
2 -2

          output 
        
复制代码NO
NO

          input 
        
复制代码5
2 -10
3 10
0 5
5 -5
10 1
5
2 -10
3 10
0 5
5 -5
10 1

          output 
        
复制代码YES
YES

数组越界类的一个问题，RUNTIME ERROR 或者ACCESS什么的一般是这种问题

起初，写了个这个来枚举题意——然后不出所料RuntimeERROR了……

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cmath>   
#include <vector>  
#include <cctype>  
#include <cstdio>  
#include <string>  
#include <cstdlib>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
#define FLT  10000
#define MAXN 20001
#define INF -99999
using namespace std;  
int Spt[MAXN];

int main()
{
	int n;
	bool flag=false;
	memset(Spt,INF,sizeof Spt);
	//memset(Who,0,sizeof Who);
	scanf("%d",&n);
	for(int ncnt=1;ncnt<=n;ncnt++)
	{
		int res=0,ran=0;
		scanf("%d%d",&res,&ran);
		Spt[res+FLT]=res+ran;
		if(Spt[res+ran+FLT]!=INF&&Spt[res+ran+FLT]==res)flag=true;
	}
	printf(flag?"YES":"NO");
	return 0;
}

然后我就在想：d_i ( - 10⁴ ≤ x_i ≤ 10⁴, 1 ≤ |d_i| ≤ 2·10⁴)

骆驼可能站在-10000~10000，但是他们的口水可以吐到-30000~30000……

然后为了试验这个题意理解清楚没就更改DEFINE的数值来检验：

复制代码

1
2
#define FLT   30000
#define MAXN  60001

然后就AC了你敢信么！

叹一口气……

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cmath>   
#include <vector>  
#include <cctype>  
#include <cstdio>  
#include <string>  
#include <cstdlib>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
#define FLT   30000
#define MAXN  60001
#define INF -129999
using namespace std;  
int n,res,ran,Spt[MAXN];

int main()
{
	bool flag=false;
	memset(Spt,INF,sizeof Spt);
	scanf("%d",&n);
	for(int ncnt=1;ncnt<=n;ncnt++)
	{
		scanf("%d%d",&res,&ran);
		Spt[res+FLT]=res+ran;
		if(Spt[res+ran+FLT]!=INF&&Spt[res+ran+FLT]==res)flag=true;
	}
	printf(flag?"YES":"NO");
	return 0;
}

想了想，这道题用俩数组应该也成，不知道有没有这种说法~姑且叫做【双数组法】好啦~

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cmath>   
#include <vector>  
#include <cctype>  
#include <cstdio>  
#include <string>  
#include <cstdlib>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
//#define spt(a) a>0?SptP[a]:SptN[abs(a)] 此句不可用，会出现spt(a)为很大的数的情况 
#define MAXN 30001
#define INF	-99999
using namespace std;  
int n,res,ran,des,SptP[MAXN],SptN[MAXN];

int main()
{
	bool flag=false;
	memset(SptP,INF,sizeof SptP);
	memset(SptN,INF,sizeof SptN);
	scanf("%d",&n);
	for(int ncnt=1;ncnt<=n;ncnt++)
	{
		scanf("%d%d",&res,&ran);
		des=res+ran;
		if(res>0)	SptP[res]=des;
		else 		SptN[abs(res)]=des;
		if(des>0)
		{
			if(SptP[des]!=INF&&SptP[des]==res)flag=true;
		}
		else if(SptN[abs(des)]!=INF && SptN[abs(des)]==res)flag=true;		
	}
	printf(flag?"YES":"NO");
	return 0;
}