赢球票

题目描述

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

主持人拿出 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

c语言

#include <stdio.h>int main()
{int n=0;scanf("%d",&n);int a[101]={0},b[101]={0},sum[101]={0};//a数组存卡片，b数组用来标记a数组的卡片是否被取走，sum数组存从那张牌开始拿的所有牌之和int i,j;for(i=0;i<n;i++){scanf("%d",&a[i]);b[i]=a[i];} int flag=0,count=0;int k;//暴力枚举每个位置的情况 for(i=0;i<n;i++){k=i;//记录第一个数的位置下标flag=1;//从1开始数 while(flag<=n)//遍历数组，并且设置跳出循环的条件，一旦flag的数值超过n，说明再也拿不到了 {while(b[k]==0)//0代表该位置的数字已经被拿走了，这里的b数组一定存在还没拿完的牌，所以能跳出循环 {k=(k+1)%n;//如果走到之前取出的位置，跳过该位置指向下一位置 }if(b[k]==flag)//找到了{b[k]=0;//找到了赋0 sum[i]+=flag;//从这个位置开始拿的所有牌之和flag=1;//下一次又从1开始 for(j=0;j<n;j++)//设置跳出while(b[k]==0)的条件，若是全部拿走，while会进入死循环 {if(b[j]!=0)break;}//如果全部被拿走了，j 就会等于 n，从而跳出循环，跳出while(flag<=n)，全都拿走了说明这就是最大值 if(j==n)break;}else{flag++;}k=(k+1)%n;//不管找没找到，k都需要+1，环形数组遍历 }for(j=0;j<n;j++)//将b数组还原，去到下一位置 {b[j]=a[j];}}int max=0;for(i=0;i<n;i++)//找出最大值 {if(max<sum[i]){max=sum[i];}}printf("%d",max);return 0;
}

c++

#include<iostream>
using namespace std;
#include<cstring>//memcpy的头文件
#include<algorithm>
const int N=1e2+10;
int n;
int a[N],b[N];int get(int k)
{int sum=0,cnt=1;memcpy(b,a,sizeof b);//sizeof b=110/*for(int i;i<n;i++)b[i]=a[i];*/while(true){while(b[k]==0)k=(k+1)%n;if(b[k]==cnt){sum+=b[k];b[k]=0;cnt=1;}elsecnt++;k=(k+1)%n;if(*max_element(b,b+n)==0)//如果 b 数组里全部为 0 ，则跳出循环 return sum;if(cnt>n)return sum;}return -1;
}int main()
{cin>>n;for(int i=0;i<n;i++)cin>>a[i];int res=0;for(int i=0;i<n;i++)res=max(res,get(i));cout<<res<<endl;return 0;
}