一、题目描述:
某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。
主持人拿出 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; } }
注意点:
1.我使用的是Java,需要导包,如果不知道导哪个包或者导的包很多,可以直接就导
import java.util.*;
表示util包下的所有子包,其次类的命名必须为 class Main
2.在进行循环选择卡片的时候记得 对n取余,防止数组下标越界
3.每次计数开始都要重新置flag为true,(判断是否有剩余卡片的数值大于count,如果没有,表
示count大于所有卡片数值,不会再有相等的了,不会再取卡片,直接跳出循环)防止上一次循环
的结果影响下一次循环造成死循环
4. 在跳过已经取走的卡片时,需要设置一个变量num记录此时已经取走的卡片数量,如果全部都
取走了就跳出循环,防止死循环