[蓝桥杯 2016 国 C] 赢球票(队列)
·

根据题目描述,我们可以得知如果当前数到的数字等于当前的球票编号就直接将当前球票赢取并且在下一个球票再次从1开始数,而我们开始选择的地方也是任意的,因此我们需要枚举所有的情况来找出赢取球票最多的情况,而对于每种情况,我们可以用队列来存储相应的值,每次遍历取出当前对头,如果对头等于当前的数字就直接赢取,如果不是就将对头放在队尾,让队列来实行动态遍历,如果数的数字大于了最大编号就直接break即可
上代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int *arr;
int check(int x, int n)//x表示从第x个位置开始,n表示数组的大小
{
queue <int> q;
for(int i = x; i <= n; i++) q.push(arr[i]);//先将后半部分加上去
for(int i = 1; i < x; i++) q.push(arr[i]);//再将前半部分加上去
int tmp = 1;//tmp表示当前的编号
int sum = 0;//sum表示当前的答案
while(!q.empty()){
int a = q.front(); q.pop();
if(a == tmp){
sum += a;
tmp = 1;
}
else{
q.push(a);//如果没有找到就直接将a放在队尾
tmp++;
}
if(tmp > n) break;//如果此时tmp > n,那么后面将不会再找到新的卡牌
}
return sum;
}
int main(void)
{
int n; cin >> n;
arr = new int[n + 10];
for(int i = 1; i <= n; i++) cin >> arr[i];
int ans = -1;
for(int i = 1; i <= n; i++){
ans = max(ans, check(i, n));
}
cout << ans << endl;
return 0;
}

更多推荐
所有评论(0)