赢球票（蓝桥杯）

赢球票

题目描述

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

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

输出

1
1

c语言

#include 

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

c++

#include
using namespace std;
#include//memcpy的头文件
#include
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
	while(true)
	{
		while(b[k]==0)
			k=(k+1)%n;
		if(b[k]==cnt)
		{
			sum+=b[k];
			b[k]=0;
			cnt=1;
		}
		else
			cnt++;
		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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48