数据结构_wow(泡泡的饭碗)
问题描述
饱了吗终于发现泡泡破解了它的代码并借此白吃白喝。饱了吗当即改变了自
己的幸运儿生成源码,但是,又被机智的泡泡偷瞄到了,机智的泡泡马上意识到
可能要饭碗不保了:
每当有人参与抽奖,这个人就进入队列。当人数达到 n 的时候开奖一次。
1. 开奖时,将执行 m 次操作,每次操作挑一个不超过 200 的数 d,且保证 d
不超过人数的一半,然后把第 D 个人和第 n-D+1 个人这两个人之间的队伍反转:
2. 反转前: 1,2,...,D-1,D,D+1,..., n-D+1, n-D+2,...n(从左往右编号)
3. 反转后: 1,2,...,D-1,n-D+1,n-D,..., D+1, D, n-D+2...n(这里的编号
是旋转前从左到右的编号)
m 次操作完后从队头开始报号,没报到 x 的回到队尾,报到 x 的就是幸运儿
啦;
机智的泡泡马上又意识到,当 n 和 m 次操作和 x 的值已知的时候,幸运儿仍
然是可以预知到是第几个参与抽奖的人的。
机智的泡泡马上又意识到,自己的饭碗保住了。
但是!机智的泡泡马上意识到一个问题,这个预知结果的代码不好打。
但是!机智的泡泡马上想起了你。
机智的泡泡马上把锅又扔给了你。
★数据输入
输入第一行为三个正整数 n, m, x。
接下来 m 行,第 i 行给出第 i 次操作的 d,如题;
对于 80%的数据, 2<=n<=2000, 1<=m<=2000;
对于 100%的数据, 2<=n<=100000, 1<=m<=100000
1<=x<=1000,000,000, 1<=d<=min(n/2,200);
★数据输出
输出幸运儿是第几个参加抽奖的人。
输入示例 | 输出示例 |
5 2 1 2 1 |
5 |
输入示例 | 输出示例 |
5 4 3 2 1 2 1 |
3 |
解题思路
假设有五个元素,对1~5与2~4哥翻转一遍,那么2~4相当于没有翻转
使用flag确定目标值是否翻转,若翻转,用对称性可推出翻转后得index
code
#include <stdio.h> int main()
{
int i;
int num,opnum,x;
int tmp;
bool flag = false; scanf("%d %d %d",&num,&opnum,&x);
x%=num;
if(x==) x=num;
for(i=; i<opnum; i++)
{
scanf("%d",&tmp);
if(tmp<=x && x<=num-tmp+)
flag = !flag;
} if(flag)
printf("%d",num-x+);
else
printf("%d",x); return ;
}
最新文章
- C#多线程之线程池篇3
- x64内核内存空间结构
- [CoreOS 转载] CoreOS实践指南(七):Docker容器管理服务
- codevs1137 计算系数
- C运行时的数据结构
- jquery实现select下拉框可输入+联想关联option
- combination-sum-ii(熟悉下Java排序)
- RAD路线规划2016版
- 《An Industrial-Strength Audio Search Algorithm》译文
- linux模块驱动之led(ioremap)
- LAMP环境快速搭建
- rsync注意事项
- Luogu 1312 【NOIP2011】玛雅游戏 (搜索)
- maven加载第三方jar不能加载
- Delphi的子类化控件消息, 消息子类化
- Mogodb 学习一
- android之Android中的SQL查询语句LIKE绑定参数问题解决办法(sqlite数据库)
- poj3061 Subsequence(尺取)
- HighCharts常用设置
- Redis缓存相关
热门文章
- Java 代码复用 —— 泛型
- UVA - 1610 Party Games (字符串比较)
- CodeForces - 138C: Mushroom Gnomes - 2 (线段树&;概率&;排序)
- [SP16549]QTREE6
- MSSQL日誌傳輸熱備份注意事項
- qq群文件管理
- poj 2262 Goldbach&#39;s Conjecture——筛质数(水!)
- LR录制https协议设置方法
- ubuntu lts install licode tag pre-v5.4
- think python chapter3