数据结构_XingYunX(幸运儿)

问题描述

　　泡泡最近下了个饱了吗 app，这个 app 推出了个坑蒙拐骗的红包系统，只要
花一块钱买张一元抵用券，就有参与 20 元红包的抽奖机会，抽奖界面会实时显
示当前参与抽奖的人数，当参与抽奖人数达到 n 的时候，开奖一次，抽取一名幸
运儿获得 20 元红包。
一次偶然的机会，机智的泡泡偷瞄到了生成幸运儿的源码：每当有人参与抽
奖，这个人就进入队列。
开奖时，每轮淘汰一个人，直到剩下一个人：每轮从第一个人开始，从 1 开
始报数。
1. 如果当前的人报的数不超过队列人数的一半，那么这个人出队，回到队
尾等待下一次报数，下一个人继续报下一个数。
2. 如果当前的人报的数超过了队列人数的一半，那么这个人出局，即未中
奖。这一轮结束，下一轮就从紧接着的下一个人开始重新开始报数。
显然最后会只剩下一个人，这个人就是幸运儿啦~
机智的泡泡马上意识到，当 n 已知的时候，幸运儿其实可以预知到是第几个
参与抽奖的人。
机智的泡泡马上又意识到，假设第 x 个参与抽奖的人是幸运儿，那么只要看
到屏幕上显示的人数达到 x-1 的时候参与抽奖，就能成为那个幸运儿啦~
机智的泡泡马上从小道消息得知了 n，正试图预知出 x 的值。
机智的泡泡马上把锅甩给了你。

★数据输入
输入第一行为一个正整数 n。
对于 50%的数据， 1<=n<=1000;
对于 80%的数据， 1<=n<=6000;
对于 100%的数据， 1<=n<=1000000000;

★数据输出
输出 x。

输入示例	输出示例
5	5

输入示例	输出示例
6	3

解题思路

　　思路1：通过观察多组数据，若输入为奇数，输出为本身；若输入为偶数，输出为一半

　　思路2（未验证）：若输入为奇数n，每次排除掉的数为 (上个排除掉的数+(n/2+1))的结果对n取模

　　　　　　　　　　若输入为偶数n，排除掉的数为（ (上个排除掉的数+(n/2+1)) 或 (上个排除掉的数+(n/2)) 再取模）轮流进行

code

 1 #include <stdio.h>
 2 
 3 int main()
 4 {
 5     int num;
 6     scanf("%d",&num);
 7     if(num%2==0)
 8         printf("%d
",num>>1);
 9     else
10         printf("%d
",num);
11     
12     return 0;
13 }
14 /*
15 1 2 3 4 5
16 3 1 4 2 5
17 +3
18 
19 1 2 3 4 5 6
20 4 1 5 2 6 3
21 +4 +3 +4 +3 +4 +3
22 
23 1 2 3 4
24 3 1 4 2
25 
26 1 2 3 4 5 6 7
27 4 1 5 2 6 3 7
28 
29 num奇数->num
30 num偶数->num/2
31 */