笔试算法题

最强的不一定是最后的赢家

• 题目描述
  某赛事有n名选手参加，但是不同于其他的比赛，本比赛采取的是擂台赛的形式，n名选手排成一排，每次队伍的第一位和第二位选手进行比赛，输的一方会排到队尾。

当某位选手取得m连胜时，他将成为最后的赢家，且游戏结束，请问截止到游戏结束，共会进行多少次比赛。

两位选手的比赛结果由他们的战斗力决定，n位选手的战斗力是一个1~n的排列，也就是说他们的战斗力两两不同，不会有平局的情况。

• 输入

输入第一行包含两个正整数n，m，分别代表参赛选手数量和取得连胜的要求。
(1<=n<=100000，1<=m<=10^9)

输入第二行包含n个正整数，中间用空格隔开，第i个数表示队伍的第i位选手的战斗力，
整体是一个1~n的排列。

• 输出

输出仅包含一个正整数，表示截止到游戏终止，共进行多少场比赛。

• 样例输入

4 2
1 3 2 4
样例输出
2

• 提示

样例解释
显然第一局应该是战斗力为3的选手获胜，第二局同样是战斗力为3的选手获胜，2连胜终止游戏，所以答案是2。
此时若修改m为3，则结果是5。

• 解题思路
  创建一个队列deque,把每个选手的战斗力依次放入队列中。
  创建两个变量cnt,cnt2.cnt用来记录每个选手的比赛场数，cnt2用来记录所有选手满足条件前的所有比赛场数。
  按照条件，输的选手放到队列的末尾

#include<iostream>
#include<queue>
using namespace std;

int main()
{
    int m,n;//m个选手,n连胜
    cin >> n >> m ;
    queue<int> q;
    int h,y,cnt2=0   ;//cnt2是共进行的比赛场数
    for(int i = 0;i< n;i++)
    {
        cin >> h;
        q.push(h);//把每个选手的战斗力存放进队列中
    }
    
    int cnt = 0;//每个选手进行多少场比赛
    h = q.front();//取第一个元素
    q.pop();
    //while循环的终止条件:比赛次数cnt>连胜次数m
    while(cnt < m)
    {
        cnt2++;
        y = q.front();
        if(h > y) //若h赢了，则h继续作为基准
        {
            cnt++;
            q.pop();
            q.push(y);
        }
        else //若y赢了，重新开始
        {
            q.pop();
            q.push(h);
            h = y;
            cnt = 1;
        }
        cout << "cnt的变化:" << cnt << endl;
    }
    cout << "共进行的比赛场数:" << cnt2 << endl; 
    return 0;
}

定义随机序列(这道题有点变态，可以不看)

• 题目描述
  给定一个数a0，定义如下随机序列: a1,a2,....,an

1. 从闭区间[0,a0]中等概率随机选出一个整数k0，令a1 = a0-k0;
2. 得到随机数a1之后，再从闭区间[0,a1]中等概率随机选出一个整数k1,再令a2 = a1-k1;
3. 一般地，得到随机数ai之后，再从闭区间[0,ai]中等概率随机选出一个整数ki，令ai+1 = ai-ki.
   问an=0的概率是多少?

• 输入

输入两个整数n,a0(1≤n,a0≤100)。

• 输出

输出概率，小数点后四舍五入保留5位小数。

• 样例输入

3 3

• 样例输出

0.72049

• 提示

输入样例2
1 3
输出样例2
0.25000

输入样例3
100 3
输出样例3
1.00000

• 解题思路
  这是一道简单的概率题，只是分析过程有点麻烦。以n=3,a0=3分析a3=0的概率？

1. a0 =3;
2. a1 = a0-k0 = 3 - {0,1,2,3}(k0有四种选择) = {3,2,1,0}
3. a2 = a1-k1 :
   a) a1 = 3,k1有四种选择{3,2,1,0}
   b) a1 = 2,k1有三种选择{2,1,0}
   c) a1 = 1,k1有两种选择{1,0}
   d) a1 =0,k1只有一种选择{0}

4. a3 = a2-k2:
   a) a2 = 3, k2只能=3。a2等于3有四种可能性分别求每种可能性的概率(P(a2=3)=1/4，P(a2=2)=1/3,P(a2=1)=1/2,P(a2=0)=1)
   b) a2 = 2,k2只能=2。a2等于2有三种可能性
   c) a2 = 1,k2只能=1。a2等于1有两种可能性
   d) a2=0,k2只能=0。 a2等于0有一种可能性

   
   image.png

• 代码
  定义二维数组a[i][j]表示ai对应的闭区间[0,ai]中[0,j]的概率。
  即我们要求的是a[3][0]，P(a3=0)=?

1. 可以先求出a1对应每个值的概率

for(int i=0;i<=a0;i++)
{
     a[1][i]=1.0/(a0+1);
 }
 if(n==1)
{
     printf("%.5f\n",a[1][0]);
     return 0;
}

2. 在a1的基础上求a2对应四种情况的不同概率值

 for(int i=2;i<=n;i++)
{
     for(int j=0;j<=x;j++)
     {
           for(int k=j;k<=x;k++)
            {
               a[i][j]+=(a[i-1][k]*(1.0/(k+1)));
           }
     }
 }

image.png
具体代码见Github