FZU Problem 2221 RunningMan（贪心）

时间：2022-06-07 21:35:07

一开始就跑偏了,耽误了很长时间,我和队友都想到博弈上去了...我严重怀疑自己被前几个博弈题给*了...贪心的做法其实就是我们分两种情况,因为A先出,所以B在第一组可以选择是赢或输,如果要输,那直接不上人,而A已经赢了一场,所以A只要再赢一场就可以了,A的最优策略是把自己剩下的全上去,即为(a,n-a,0)的形式,B的最优为(0,m-1,1)的形式,若A要赢就是(n-a) >= (m-1).如果B选择在第一场赢的话,那B应该在第一场放上a+1个人,A的最优为(a,(n-a)/2,(n-a)/2)的形式,因为不能多放也不能少放,(话说多放了不就是少放了吗..),所以平均是最优的,B的最优形式(a+1,m-a-1,0),A要赢的话就是(n-a)/2 >= m-a-1,最后得出n >= 3*(m-1) / 2;

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int main()

{

    int t;

    scanf("%d",&t);

    double n,m;

    while(t--)

    {

        scanf("%lf%lf",&n,&m);

        if(n >= *(m-)/)

        puts("Yes");

        else puts("No");

    }

    return ;

}

上面是一种做法,也可以讨论m的奇偶性,若m为奇数,则m可以表示为2*k + 1 = m,此时若A的形式为(k,k,k)则A总能赢两局,若m为偶数,则m = 2*k,此时A为(k,k,k-1)时A必赢两局,一种较为极端的考虑方式,满足n >= 3*k即可(需要注意讨论m的奇偶).

相关文章