【蓝桥杯】真题练习——赢球票

简介: 蓝桥杯真题训练——赢球票

一、题目描述:

某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。


 主持人拿出 N 张卡片(上面写着 1~N 的数字),打乱顺序,排成一个圆圈。你可以从任意一张

卡片开始顺时针数数: 1,2,3..... 如果数到的数字刚好和卡片上的数字相同,则把该卡片收入囊

中,从下一个卡片重新数数。 直到再无法收获任何卡片,游戏结束。囊中卡片数字的和就是赢得

球票的张数。

比如:

 卡片排列是:1 2 3

 我们从1号卡开始数,就把1号卡拿走。再从2号卡开始,但数的数字无法与卡片对上,很快数字

越来越大,不可能再拿走卡片了。因此这次我们只赢得了1张球票。还不算太坏!如果我们开始就

傻傻地从2或3号卡片数起,那就一张卡片都拿不到了。

如果运气好,卡片排列是 2 1 3

那我们可以顺利拿到所有的卡片!

本题的目标就是:已知顺时针卡片序列。


随便你从哪里开始数,求最多能赢多少张球票(就是收入囊中的卡片数字之和)

输入格式

  第一行一个整数N(N<100),表示卡片数目

  第二行 N 个整数,表示顺时针排列的卡片

输出格式

  一行,一个整数,表示最好情况下能赢得多少张球票


  用户输入:

  3

  1 2 3


  程序应该输出:

  1

  用户输入:

  3

  2 1 3


  程序应该输出:

  6

二、问题分析

题目文字描述很多,简单分析总结下,从 1-N 中任意选择一个数开始 从1顺时针计数,当计数数值

与卡片上的数值也就是1-N中的数值相等时,就拿走这个卡片(获得卡片上的数值),从下一张卡片

重新从1开始计数,问最大获得卡片的数值和

1. 根据题意,我们首先想到的就是枚举所有可能的情况,求出最大值,这也正是这道题的解题思

路。实际上蓝桥杯枚举的题目经常考察。 明确使用枚举思路后,关键是如何进行枚举,以及枚举

时候的细节。

2.我们从第1张卡片开始进行枚举,并不断进行计数,如果计数和卡片数值相等加上卡片的数值

(也可以是count的值),问题来了,如果满足条件拿走这张卡片,继续枚举时需要跳过这张卡

片,我们如何知道这张卡片已经取走了呢?

3.我们可以使用变量进行标记,但是多个卡片,我们就需要多个变量进行标记,这个时候我们就想

到了使用数组,可以重新开一个新数组专门用来标记,也可以使用记录卡片位置的数组,如果取走卡

片,该位置的值就置为 -1,这样如果在枚举时遇到-1就直接跳过

4.如果使用一个数组,那么我们枚举从某一张卡片开始计数结束之后,我们继续枚举下一张卡片开

始计数,这个时候如果我们肯定不能使用上一次处理后的数组,因此我们需要每次枚举一张开始的

卡片就要重新使用一个临时数组,该数组等于最初输入的卡片顺序

5.每次枚举都使用一个变量sum记录本次获得的数值,本次枚举结束之后进行更新max记录最大值

三、代码实现

Java代码实现

import java.util.Scanner;
class Main{
  //定义全局数组nums 和 数组长度 n 方便函数调用
   static int[] nums;
   static int n;
    public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
       n = sc.nextInt();
      nums = new int[n];
      for(int i = 0;i <n;i++) {
        nums[i] = sc.nextInt();
      }
      System.out.println(getMax());
    }
   static int getMax() {
    int max = 0;
    for(int i = 0;i < n;i++) {
      //每次重新选择一行牌作为起始  都要重新设置临时数组
      int[] temp = new int[n];
      //初始化临时数组
      for(int k = 0;k < n;k++) {
        temp[k] = nums[k];
      }
      //计数
      int count = 1;
           //记录一次枚举获得的卡片数值和
      int sum  = 0;
           // 标记是否count大于所有剩余卡片数值,如果true即已经不能再取卡片的跳出循环进行下一 
           // 次枚举
      boolean flag = true;
            // 开始计数的卡片对应的位置下标
      int start = i;
      while(true) {
                 // 每次循环重置flag标识
         flag = true;
                    //判断是否有剩余卡片的数值大于count,如果没有那么不会再取卡片直接跳出循环
        for(int k = 0;k < n; k++) {
          if(temp[k] >= count) {
            flag = false;
                break;          
          }
        }
        //如果count大于所有数组中的数,那么不能继续数下去了
        if(flag) break;
        int j = start ;
        //如果计数count 等于 卡片的数值 temp[j]
        if(count == temp[j]) {
          sum += count;
          temp[j] = -1;
          count = 1;
        }else {
                //计数count 不等于 卡片的数值 count+1 
          count++;
        }
        //不管是否取走卡片都要继续进行顺时针的下一张卡片
        start = (start+1) % n;
        //num用来记录此时已经取走的卡片数量,防止全部取走后 一直进行while循环
         int num = 0;
        //跳过已经取走的卡片
        while(temp[start] == -1) {
          start = (start+1) % n;
          num++;
          //防止死循环
          if(num > n ) break;
        }
      }
      //每次枚举一张卡片开始就更新下 max值
      max = Math.max(max, sum);
    }
    return max;
  }
}

image.gif

注意点:

1.我使用的是Java,需要导包,如果不知道导哪个包或者导的包很多,可以直接就导

import java.util.*;

image.gif

表示util包下的所有子包,其次类的命名必须为 class Main

2.在进行循环选择卡片的时候记得 对n取余,防止数组下标越界

3.每次计数开始都要重新置flag为true,(判断是否有剩余卡片的数值大于count,如果没有,表

示count大于所有卡片数值,不会再有相等的了,不会再取卡片,直接跳出循环)防止上一次循环

的结果影响下一次循环造成死循环

4. 在跳过已经取走的卡片时,需要设置一个变量num记录此时已经取走的卡片数量,如果全部都

取走了就跳出循环,防止死循环

相关文章
|
算法
蓝桥杯:真题 迷宫
蓝桥杯:真题 迷宫
73 0
|
6月前
|
测试技术
题目1444:蓝桥杯2014年第五届真题斐波那契
题目1444:蓝桥杯2014年第五届真题斐波那契
55 0
|
机器学习/深度学习 测试技术
|
机器学习/深度学习 人工智能
|
机器学习/深度学习
蓝桥杯真题练习
蓝桥杯真题练习
161 0