P1152 欢乐的跳

admin

https://www.luogu.com.cn/problem/P1152

题目描述
一个n个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了[1,n-1]之间的所有整数，则称之符合“欢乐的跳”，如数组1 4 2 3符合“欢乐的跳”，因为差的绝对值分别为：3,2,1。

给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

输入格式
每组测试数据第一行以一个整数n(1≤n≤1000)开始，接下来nn个空格隔开的在[-10^8−10^8]之间的整数。

输出格式
对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出"Jolly"，否则输出"Not jolly"。

输入输出样例
输入 #1
4 1 4 2 3
输出 #1复制
Jolly
输入 #2复制
5 1 4 2 -1 6
输出 #2复制
Not jolly

admin

此题的主要任务是判断相邻的两个数的差值是不是覆盖了1-(n-1)这些数字，就像三连击里面那个一样，我们可以用一个数组b(i)表示0到n-1之间的数是否吹出现过，他的初值都是0，出现了就变成1，最后看看b数组中b(1)到b(n-1)是否全部是1，只要他们全部加起来的总和是n-1的话，那就说明里面全部是1，没有一个0。（这种做法和我以前那个三连击里面的做法有点不一样，也是正确的）

1. #include <iostream>
   
2. #include <cmath>
   
3. using namespace std;
   
4. const int mm=1010;
   
5. int n,a[mm],b[mm],i,s,x;
   
6. int main()
   
7. {
   
8.         cin>>n;
   
9.         for (int i=0; i<=n; i++) b[i]=0; //表示i这个数字没有出现
   
10.         for (int i=1; i<=n; i++) cin>>a[i];
    
11.         for (int i=2; i<=n; i++)
    
12.         {
    
13.                 x=abs(a[i]-a[i-1]);
    
14.                 if (x<=n) b[x]=1; /// 为什么x<=n???  避免越界  x>mm怎么办！！
    
15.         }
    
16.         s=0;
    
17.         for (i=1; i<=n-1; i++)  s+=b[i]; ///理想下每个都是1 加起来总和n-1
    
18.         if (s==n-1) cout<<"Jolly";
    
19.         else cout<<"Not jolly";
    
20.         return 0;
    
21. }

复制代码

admin

这个题还有一个技巧，就是没有必要用a数组去存放所有的数，我们读入数据的时候就做减法，保存这个差值，而不需要保存每个数，当然，这个技巧有点吹毛求疵，要求比较高。

1.         cin>>n;
   
2.         for (int i=0; i<=n; i++) b[i]=0; //表示i这个数字没有出现
   
3.         cin>>x1;///读入第一个数
   
4.         for (int i=1; i<=n; i++)
   
5.         {
   
6.                 cin>>x2; ///读入新数
   
7.                 x=abs(x1-x2); ///后数减前数
   
8.                 if (x<=n) b[x]=1; /// 为什么x<=n???  避免越界  x>mm怎么办！！
   
9.                 x1=x2;   ///后数变前数
   
10.         }

复制代码

admin

这个题还有一个技巧，就是没有必要用a数组去存放所有的数，我们读入数据的时候就做减法，保存这个差值，而不需要保存每个数，当然，这个技巧有点吹毛求疵，要求比较高。

1.         cin>>n;
   
2.         for (int i=0; i<=n; i++) b[i]=0; //表示i这个数字没有出现
   
3.         cin>>x1;///读入第一个数
   
4.         for (int i=1; i<=n; i++)
   
5.         {
   
6.                 cin>>x2; ///读入新数
   
7.                 x=abs(x1-x2); ///后数减前数
   
8.                 if (x<=n) b[x]=1; /// 为什么x<=n???  避免越界  x>mm怎么办！！
   
9.                 x1=x2;   ///后数变前数
   
10.         }

复制代码