P8641 [蓝桥杯 2016 国 C] 赢球票--环形结构问题

题目

解析

给定一个顺序的排列，可按一定顺序数数，若数数与排列的值相同可取走，去走后，从下一个重新数数，求不同的数数顺序的最大值

想的就是暴力解答，遍历从每一个数字开始数的情况，求最大值。

环形结构的核心流程：

1.枚举起始点：尝试从每个卡片开始。
2.初始化状态：每次重置标记数组和计数器。
3.循环遍历环形结构：
4.根据当前位置的状态决定是否处理。
5.符合条件时取走卡片，更新状态和计数器。
6.环形移动到下一个位置。
7.终止条件：当无法继续取卡时停止。

代码框架参考：

for (int s = 1; s <= n; s++) {         // 枚举起始点
    int x = 1, sum = 0, cnt = 0, i = s;
    memset(v, 0, sizeof(v));           // 重置状态
    while (1) {
        if (!v[i]) {                   // 卡片未取走
            if (x == a[i]) {           // 符合取卡条件
                sum += a[i];
                cnt++;
                v[i] = 1;              // 更新状态
                x = 0;                 // 重置计数器
            }
            x++;                       // 继续数数
        }
        if (x > n || cnt == n) break;  // 终止条件
        i = (i == n) ? 1 : i + 1;      // 环形移动
    }
    ans = max(ans, sum);
}

//while()-break；和i=i==n?1:i+1;的使用是环形结构的核心

代码

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
using namespace std;
int n, v[110], a[110], ans = INT_MIN;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int s = 1; s <= n; s++) {
		//重置数据
		int x = 1, sum = 0, cnt = 0, i = s;
		memset(v, 0, sizeof(v));
		while (1) {
			if (!v[i]) {
				if (x == a[i]) {
					cnt++;//记录取的次数
					sum += a[i];
					x = 0; //数数，x的重置
					v[i] = 1; //标记已取
				}
				x++;//数数
			}
			if (x > n || cnt == n)//数数超过最大值或已取完
				break;
			i = i == n ? 1 : i + 1; //环形结构核心：确定i的位置
		}
		ans = max(ans, sum);
	}
	cout << ans;
	return 0;
}