[算法练习26-1-19]赢彩票

赢球票

题目描述

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

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

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

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

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

比如：

卡片排列是：1 2 3

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

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

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

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

输入描述

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

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

输出描述

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

输入输出示例

示例

输入

1
2
3
123

输出

1
1

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 256M

题解

该题运用模拟和枚举进行求解。

枚举每种可能 即从第1张开始数到从第N张开始数 一共N种情况

对每种情况进行模拟

第n次模拟即为从第n张牌开始数，直到数到当前序号与牌点数相同时，拿走该牌，当前模拟的总计数自加该牌点数

从下一张牌开始从头数 若遇到队尾则回到队头

直到牌全部拿走或者当前数到的序数大于最大牌的点数

所有情况模拟完毕后 选出总计数最大的那一个即为所求

代码

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;

int n, ma, t, res[101];//n:牌的总数 ma:牌的最大点数 t:当前模拟的总计数 res[]:每次模拟计数的数组
list<int> node;//循环队列 记录所有牌
list<int> ll;//记录的是当前模拟下剩余的牌

//返回从第n张牌开始数时，第一次数到的牌的迭代器
list<int>::iterator get(int n){
	auto it = ll.begin();
	for(int i = 1; i < n; i++){
		it++;
        //若遍历到队尾 则返回为队头
		if(it == ll.end()) it = ll.begin();
	}
	return it;
}

//程序枚举主代码
void st(auto it){
    //递归终止条件1：当前牌堆中已无牌
	if(ll.size() < 1) return;
    
	for(int i = 1; i <= ma; i++){
        //比较当前数的数是否与当前牌的点数一致
		if(*it == i){
			//总计数加上该牌点数
            t += *it;
            //删除该牌
			auto next = ++it;
			if(next == ll.end()) next = ll.begin();
			ll.erase(--it);
			it = next;
            //递归终止条件2：点数与当前序数一致
			//递归 从下一张牌开始从头数
            st(it);
			return;
		}else{
            //指向下一张牌
			it++;
			if(it == ll.end()) it = ll.begin();
		}
	}
    //递归终止条件3：for循环结束(当前数的数已经大于最大点数)
	return;
}         
 
int main(){
	//输入
	cin >> n;
	for(int i = 1; i <= n; i++){
		int a;
        //获取最大点数
		if(a > ma) ma = a;
		cin >> a;
		
		node.push_back(a);
	} 	
	
    //枚举 从第一张牌开始数到从第N张牌开始数的一共n种情况
	for(int i = 1; i <= n; i++){
        //还原牌堆
		ll = node;
        //获取当前情况第一张牌的指针
		auto it = get(i);
		st(it);
        //记录当前情况的总计数
		res[i] = t;
        //还原计数器
		t = 0;
	}
	//排序计数数组
	sort(res+1,res+n+1);
    //输出最大值
	cout << res[n];
	
	return 0;
}