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;
}