Description
    Lrc为了提高Scau_acm的知名度，决定赞助学校举行一场公平（heimu），公正（heimu），公开（heimu）的有奖游戏，游戏规则如下：
游戏玩家由所有参加者组成，每一回合，主持人会发布一道问题，参加者根据个人喜好，选择回答“是”或者“否”，工作人员会分别统计选“是“，跟选”否“的人数，
然后选的人数多的一方将会被淘汰，如果两方的人数相同或者全部人都选”是“或者全部人都选”否“则这回合不算，这回合重新来过，直到两方人数不同为止，剩下的
人将会留下来继续下一回合，直到只剩下1个人或者2个人的的时候，游戏结束，最终留下来的人，就是本游戏的胜利者，胜利者将会获得由Lrc赞助的丰厚奖金。
    可是Lrc又不想把奖金拱手让人，所以Lrc决定派一些手下假扮参赛者混进游戏中，那么Lrc至少要派遣多少个手下混到参赛者中才能妥妥地把所有的奖金收回来呢？
Lrc最近忙着理财没空想这问题，所以拜托身为acmer的你来编程解决这个问题。

（出题人Hq）



输入格式
第一行输入一个整数t，表示有t组输入；
每组输入包含一个整数n(2<n<1000000000)，表示有n个参赛者（包括Lrc的手下）；


输出格式
对应每组输入，输出一个整数，表示在这n个人中至少潜伏了多少个lrc的手下；


输入样例
2
3
5


输出样例
2
4

试过很多次了，就是不知道题目是怎么判定的

将数字拆分成两个差值最小的数字
例如 3 可以拆成0,3 1,2 取差值最小的 即为 1,2 那么2名间谍即可
同样 如果输入为5 可以拆成 2,3 干掉3这部分 需要 2 名间谍 剩下 2
    人 可以拆成 0,2 干掉2这部分 需要2名间谍 结束
其实 就是求数据能被拆掉的次数 n 再 乘 2

３楼解释的还是不太懂。说个具体的例子，假如是四个人答题（四个都不是间谍），两个答“是”，两个答“否”，那么要多少个间谍怎样干掉他们啊？

数学知识在编程中作用极大。。

#include <stdio.h>

int main(void)
{
    unsigned int n = 0;    ///< 数量
    unsigned int j = 0;    ///< 总的人数
    unsigned int cnt = 0;    ///< 计数器
    
    
    scanf("%u", &n);
    
    // f(n) = (f(n-1)/2) * 2 + 2 * f(1); n > 2, f(1) <= 2
    while ( n-- ){
        
        cnt = 0;
        scanf("%u", &j);
        while (j > 2){
            
            j = (j - 1)/2;
            ++cnt;
        }
        
        cnt = cnt * 2;
        if (j == 2){
            
            cnt += 2;
        }
        
        printf("%u\n", cnt);
    }
    
    return 0;
}

$ ./test
2
6
4
1000000000
58

那么Lrc至少要派遣多少个手下混到参赛者中才能妥妥地把所有的奖金收回来呢？

题目是要求所有~6个人参赛4个卧底不能保证所有~只能保证最后两位中的其中一位是卧底~

抽屉原理~

[此贴子已经被作者于2017-3-28 09:29编辑过]

根据你的思路 打的代码，不知道对不对
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int d[100005];
int f(int n)
{
    if(n<=100000&&d[n]) return d[n];
    if(n>3)
    {
        if(n%2) return f((n-1)/2)+f((n+1)/2);
        else return f(n/2-1)+f(n/2+1);
    }
    else return 2;
}
void sol()
{
    int n;
    scanf("%d",&n);
    printf("%d\n",f(n));
}
int main()
{

    for(int i=1;i<20;i++)
        d[i]=f(i);
    for(int i=20;i<=100000;i++)
    {
        if(i%2) d[i]=d[(i-1)/2]+d[(i+1)/2];
        else  d[i]=d[i/2-1]+d[i/2+1];
//    printf("%d\n",d[i]);
    }
    int t;
    scanf("%d",&t);
    while(t--)
    sol();
    return 0;
}

提交上去就错了

提交上去错了

我也是推理出来未必正确~感觉自己也不一定能做出来~有时间我再想想看~