Day 0x12 UVa10038 Jolly Jumpers

• Virtual Judge
• ZeroJudge

题意

• 输入一串数字，输出是否为 Jolly Jumper
• 需要注意的有：
  1. 每笔测资第一个整数代表有 n 个数字
  2. Jolly Jumper 定义
     • 数列中相邻数字的差分别为 1～n-1 (顺序没差)
  3. 输出格式
     • Jolly
     • Not jolly

解法

• 重复读入 n 後用 for 回圈分别存入整数阵列里

  int n;
  
  while(scanf("%d", &n) != EOF){
  
      int arr[3000] = {0};
  
      for(i = 0; i < n; i++){
          scanf("%d", &arr[i]);
      }
  }
  

• 计算每两数之间的差并存入阵列里

  int S[3000] = {0};
  
  for(i = 0; i < n - 1; i++){
      S[i] = abs(arr[i] - arr[i + 1]);
  }
  

• 对差值的阵列进行排序

  for(i = 0; i < n - 1; i++){
      for(j = i + 1; j < n - 1; j++){
          if(S[i] > S[j]){
              temp = S[i];
              S[i] = S[j];
              S[j] = temp;
          }
      }
  }
  

• 用 for 回圈检查是否 1～n-1 都有对应的差值；若有不同便跳出回圈，根据 flag 的状态输出结果

  for(i = 0; i < n - 1; i++){
      if(S[i] != i + 1){
          flag = true;
          break;
      }
  }
  
  if(flag){
      printf("Not jolly\n");
  }
  else{
      printf("Jolly\n");
  }
  

• C code

  #include<stdio.h>
  #include<stdbool.h>
  
  int main(){
  
      int n;
      int i, j;
      bool flag;
      int temp;
  
      while(scanf("%d", &n) != EOF){
  
          int arr[3000] = {0};
  
          for(i = 0; i < n; i++){
              scanf("%d", &arr[i]);
          }
  
          int S[3000] = {0};
  
          for(i = 0; i < n - 1; i++){
              S[i] = abs(arr[i] - arr[i + 1]);
          }
  
          for(i = 0; i < n - 1; i++){
              for(j = i + 1; j < n - 1; j++){
                  if(S[i] > S[j]){
                      temp = S[i];
                      S[i] = S[j];
                      S[j] = temp;
                  }
              }
          }
  
          flag = false;
  
          for(i = 0; i < n - 1; i++){
              if(S[i] != i + 1){
                  flag = true;
                  break;
              }
          }
  
          if(flag){
              printf("Not jolly\n");
          }
          else{
              printf("Jolly\n");
          }
      }
  
      return 0;
  }
  

• C++
  • 可用 sort 加快速度；vector 或 map 等 STL 快速查找与动态储存

  #include <bits/stdc++.h>
  using namespace std;
  
  int main(){
  
      int n;
      int i;
      bool flag;
      int temp;
  
      while(cin >> n){
  
          vector<int> v;
          vector<int> d;
  
          for(i = 0; i < n; i++){
              cin >> temp;
              v.emplace_back(temp);
          }
  
          for(i = 0; i < n - 1; i++){
              d.emplace_back(abs(v[i] - v[i + 1]));
          }
  
          sort(d.begin(), d.end());
  
          flag = false;
  
          for(i = 0; i < n - 1; i++){
              if(d[i] != i + 1){
                  flag = true;
                  break;
              }
          }
  
          if(flag){
              cout << "Not jolly\n";
          }
          else{
              cout << "Jolly\n";
          }
      }
  
      return 0;
  }