蓝桥杯题目---赢球票_c++真题赢球票-CSDN博客

admin 1个月前 (04-16) 社区服务 15 0

　　这是一个经典的约瑟夫问题，可以使用数学方法进行求解。假设卡片排列是1, 2, 3, ..., N，我们从第K张卡开始数，每次数M个，那么最后剩下的卡片编号为：

　　((K-1)+M) % N + 1, ((K-1)+2M) % N + 1, ((K-1)+3M) % N + 1, ..., ((K-1)+(N-1)M) % N + 1

　　为了使得拿到的卡片数最多，我们需要找到一个最大的M，使得所有剩下的卡片编号之和最大。这个问题可以通过枚举K和M来解决，时间复杂度为O(N^2)。但是还有更快的算法。

　　首先，我们可以把问题转化为求剩下的卡片编号之和最小。这是因为，如果我们从第K张卡开始数，每次数M个，拿到的卡片编号和为S，那么剩下的卡片编号和就是1+2+...+N-S，也就是(N+1)N/2-S。因此，如果我们能找到一个最小的剩下卡片编号和，就可以通过(N+1)N/2减去它得到拿到的卡片编号和的最大值。

　　接下来，我们考虑如何快速求解剩下的卡片编号之和的最小值。假设我们从第i张卡开始数，每次数M个，得到的剩余卡片编号为：

　　(i+M-1) % N + 1, (i+2M-1) % N + 1, ..., (i+(N-1)M-1) % N + 1

　　我们可以把它们按照卡片编号从小到大排序，得到一个新的序列：

　　j1, j2, ..., jN

　　其中，j1, j2, ..., jN是1, 2, ..., N的一个排列，满足：

　　(i+(j1-1)M) % N + 1 <= (i+(j2-1)M) % N + 1 <= ... <= (i+(jN-1)M) % N + 1

　　我们把这个排列称为“最小化序列”。注意到，不同的i和M得到的最小化序列可能不同，但是它们都可以通过某种旋转方式相互转化。因此，我们只需要找到最小化序列中的最小值，即可得到剩下的卡片编号之和的最小值。

　　接下来，我们考虑如何快速求解最小化序列中的最小值。假设最小化序列为：

　　j1, j2, ..., jN

　　我们把它扩展成一个长度为2N的序列：

　　j1, j2, ..., jN, j1, j2, ..., jN

　　然后，我们可以使用动态规划的方法求解最小值。令f(i,j)表示从序列中的第i个位置开始，长度为j的子序列中的最小值。显然，f(i,j)可以通过f(i,j/2)和f(i+j/2,j/2)求解。具体地，我们可以考虑分两种情况：