蓝桥杯2015年第六届真题-赢球票

题目

题目链接

题解

暴力+模拟。

枚举每次从哪个位置开始，也就是有n种情况要枚举；
对于每一种情况，我们都模拟这个过程，更新最大值，取牌操作结束的条件是还未被取走的数中的最大值都小于报的数了，说明没有办法取走任何一张了，此时结束；
注意答案要求获取的牌上的值之和，而不是牌数。

代码中：
a数组是初始的输入数组，是一程不变的；
c数组存储的是每次枚举从哪个位置的数组，存储每种情况；
b数组算是临时数组，用于暂存每轮报数结束后还剩哪些数未被取走，本轮结束后会赋值回c数组中；
cnt表示c数组牌的个数；
nowcnt表示本轮中未被取走的牌数，也是用于暂存，之后会赋值给cnt。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;

int n, cnt, ans, sum;
int  a[N], c[N], b[N];

int main()
{
	cin>>n;
	cnt = n;
	for(int i = 1;i <= cnt;i ++) cin>>a[i], sum += a[i];

	for(int pos = 1; pos <= n;pos ++) { // 获取数组c 
		for(int i = 1;i <= n;i ++) 
			if(i == pos) {
				int nowcnt = 0;
				for(int j = i;j <= n;j ++) c[++nowcnt] = a[j];
				for(int j = 1;j < i;j ++) c[++nowcnt] = a[j];
				break;
			}
		
		int num = 1, mx = INF, cnt = n;
		while(mx >= num) { // 模拟过程，当c数组中的最大值都没报的数大了，说明结束了 
			int nowcnt = 0;
			mx = 0;
			for(int i = 1;i <= cnt;i ++) {
				if(num == c[i]) {num = 1; continue;} // 报的数与c数组中的数相等，重新报数 
				b[++nowcnt] = c[i], mx = max(mx, c[i]); // b用于存储这轮结束后还剩哪些数未被取走 
				num ++;
			}
			cnt = nowcnt; // 还剩多少数未被取 
			for(int i = 1;i <= cnt;i ++) c[i] = b[i]; // 将b数组赋值回数组c 
		} 
		
		int tsum = 0;
		for(int i = 1;i <= cnt;i ++) tsum += c[i]; // 统计未被取走的数之和 
		ans = max(ans, sum - tsum); // 更新最大值 
	}
	cout << ans << endl;

	return 0;
}