题目链接

目录

题目描述

输入描述

输出描述

输入输出样例

样例1

样例2

 题目分析：

        样例1：

        样例2：

        整体思路：

AC代码（Java）:

---

题目描述

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

        主持人拿出 N 张卡片（上面写着 1⋯N 的数字），打乱顺序，排成一个圆圈。

        你可以从任意一张卡片开始顺时针数数: 1,2,3 ⋯⋯

        如果数到的数字刚好和卡片上的数字相同，则把该卡片收入囊中，从下一个卡片重新数数。

        直到再无法收获任何卡片，游戏结束。囊中卡片数字的和就是赢得球票的张数。

        比如： 卡片排列是：1 2 3。

        我们从 1 号卡开始数，就把 1 号卡拿走。再从 2 号卡开始，但数的数字无法与卡片对上，很快数字越来越大，不可能再拿走卡片了。因此这次我们只赢得了 1 张球票。

        还不算太坏！如果我们开始就傻傻地从 2 或 3 号卡片数起，那就一张卡片都拿不到了。

        如果运气好，卡片排列是 2 1 3，那我们可以顺利拿到所有的卡片！

        本题的目标：已知顺时针卡片序列，随便你从哪里开始数，求最多能赢多少张球票（就是收入囊中的卡片数字之和）

输入描述

        第一行一个整数 N (N≤100)，表示卡片数目。

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

输出描述

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

输入输出样例

        我多放一个样例，帮助大家理解，比赛很多时候都是只给出一个样例，所以我们要认真审题，理解题意。

样例1

输入

3
1 2 3

输出

1

样例2

输入

5 
1 3 5 2 4

 输出

15

 题目分析：

        我们先拿样例1和2来进行分析，同时方便大家理解。

        样例1：

        

         我们这时候有三个卡片，卡片的顺序如下，假如我们从第一个卡片开始数数（从1数到N，我把我们数的这个数叫做cur吧），如果卡片对应的数字和cur相同，那么就拿走这个卡片。

        如：

        因为我们拿走了一张卡片，我们就要重新从1开始数数，也就是令cur=1。 

        因为第一张卡片被我们拿走了，接下来我们只能从第二个卡片开始数数了。

       

         因为cur的值和第二个卡片的数字不相同，所以我们不能拿走这张卡片，我们需要继续往下数数。

        

        因为第一个卡片已经被我们拿走了，所以第三个卡片的下一个卡片应该就是第二个卡片，这也就是题目说的 顺时针卡片序列 的意思。

        接着看：

        cur和第二个卡片不相同，我们需要继续往下数数：

         

         当cur=4的时候，我们还需要往下数数嘛？应该不需要了吧，因为我们卡片最大也就是3，所以如果cur>3了，后面怎么数都不可能会有卡片的数字相同了，这时候就可以结束我们的数数了。

        如果还不明白，接下来我继续演示一下样例2为什么会得出15，如果看懂了，就可以自己去尝试写一下了哦。

        样例2：

        整体思路：

                因为涉及到频繁的删除，所以我们需要使用到列表来存储数据，每次我们拿走卡片，对应的就是删除列表中的当前元素。

                因为题目允许我们从任意一张卡片开始数数，也就是我们可以从列表之中的任意一个下标开始模拟数数这个过程，只需要找到我们可以拿到的卡片数字总和（每张卡片的值相加）。

                我们数数是从1开始的，一直向后数。但是我们的列表是有限的，所以我们需要一个变量来遍历列表，每次都要对这个变量进行求余，也就是 变量  = 变量 % 列表的长度。这样可以保证这个变量一直是在列表里面循环的。

                我们每次拿出卡片，也就是删除列表的元素之后，我们需要重新从1开始数数，也就是我上面提到的 令cur=1  ，这样重新开始数数。

                本题不难，主要是理解题目的意思就好。

AC代码（Java）:

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static int n;static int res;public static void main(String[] args) {List<Integer> list = new ArrayList<>();//拿数据Scanner scan = new Scanner(System.in);n = scan.nextInt();for(int i = 0;i<n;i++) {int targe = scan.nextInt();list.add(targe);}scan.close();//每一个位置都需要搜索一次for(int i = 0;i<list.size();i++)find(new ArrayList<>(list),i);System.out.println(res);}//从startIndex开始数数,每次如果拿走了一个卡片，就要重修从1开始数数，从下一个开始数public static void find(List<Integer> list , int startIndex){int max = 0;int cur = 1; //我们需要从1开始数数,每次我们拿走了一个卡片，就要从下一个卡片，开始从1数继续数while(cur<=n && startIndex<list.size()){ //当cur大于n时候，代表我们的列表之中再也没有一个可以拿出来的卡片了//这里可以写剪枝，但没有必要(数据量不多)，如果写，那就是记录当前list中的最大值，如果cur超过最大值，就结束循环if(list.get(startIndex) == cur){max += cur;cur = 1; //拿走卡片之后，要从1开始重新数数//然后删除当前这个位置list.remove(startIndex);}else {cur++;startIndex++;}//已经全部拿完了，就直接结束循环if(list.size() == 0) break;//我们需要控制startIndex的范围是在list的长度范围之内startIndex %= list.size();}//更新resres = Math.max(res,max);}
}