蓝桥杯练习系统（算法训练）ALGO-973 唯一的傻子

本文主要是介绍蓝桥杯练习系统（算法训练）ALGO-973 唯一的傻子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

资源限制

内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

问题描述

　　腿铮找2255有点事，但2255太丑了，所以腿铮不知道他的长相。正愁不知道到如何找他的时候，他突然看见计33班围成了一个圈在领微积分试卷。计33班有n个人，其中班长编号为0，其余同学依次按顺时针方向编号。
　　只听见计33小导说“x号同学顺时针方向往后数的第k个的神犇出列（不包括x号同学），领取满分试卷！”。剩下的人继续围成一个小圈。这样一个过程持续了n-1次，那么显然，最后只剩下了一个人。众所周知，2255是个大傻子，门门挂科，不符合满分试卷这一前提条件。通过这样一个过程，腿铮终于找到了2255并血虐了他。
　　求2255的编号是多少。

输入格式

　　第一行一个n，表示计33班的人数。
　　接下来n-1行，表示小导说话中的x和k。

输出格式

　　一个数字，表示2255的编号。

样例输入

3
1 1
0 1

样例输出

数据规模和约定

　　前90%数据保证n<=10^4.
　　前100%数据保证n<=10^6，1<=k<min(当时圈中人数,1000)

法一：

#include<iostream>
using namespace std;int main(){int n;scanf("%d",&n);int x,k;for(int i=0;i<n-1;i++){scanf("%d%d",&x,&k);}printf("%d\n",x);return 0;
}

思路：剩下的最后一个即为2255，所以第n-1次输入的两个数中一定有2255，而他是剩下的，因此要删除另一个，所以，前面的那个就是2255。

法二：

#include<iostream>
using namespace std;
const int N=10e6+10;
int st[N];
int main(){int n;scanf("%d",&n);for(int i=0;i<n-1;i++){int a,b;scanf("%d%d",&a,&b);int j=a;//指针j指向ab=b%n;int cnt=1;while(cnt<=b){if(st[(j+cnt)%n]==0){if(cnt==b){st[(j+cnt)%n]=1;break;}cnt++;}else{j++;}}}for(int i=0;i<n;i++){if(st[i]==0){cout<<i<<endl;}}return 0;
}

思路：一个个遍历。每次走有效的k步（被删除的也要走，但是是无效的），但是会运行超时。