6784. Game

HDOJ 6784. Game

2020 年百度之星·程序设计大赛 - 初赛三

• 6783. Discount
• 6784. Game
• 6785. Permutation
• 6786. Intersection

题目：6784. Game

问题描述：

Alice 和 Bob 在玩游戏。

桌面上有两堆金币，少的那堆有 x 个金币，多的那堆有 2x 个金币。

假设金币可以被无限细分。Alice 和 Bob 事先都不知道 x 是几，但是他们都知道 x 是一个 (0,1] 之间均匀分布的随机实数。

Alice 会等概率的被分配到其中的一堆金币，Bob 会得到另一堆。xx 的值和两堆金币的分配是相互独立的。

拿到金币以后，Alice 会马上数清自己拿到多少金币。然后 Alice 可以选择是否和 Bob 那堆换。

给定 Alice 拿到的金币数目，请问 Alice 要不要交换，使得她期望能得到的金币数目更多？

如果交换期望得到的金币数目多于不交换期望得到的金币数目，输出交换，否则不交换。

输入：

第一行一个正整数 test (1≤test≤200000) 表示数据组数。
接下来每行一个小数 p (0<p≤2)，p 最多保留五位小数，表示 Alice 拿到的金币数目。

输出：

对于每组数据，输出 Yes 表示需要交换，输出 No 表示不要交换。

样本输入：

1
1.00000

样本输出：

Yes

方法：博弈

思路：博弈问题，因为x是(0,1]的，p是(0,2]的，又由于当p>1的时候Alice肯定是拿的大的部分不用换，否则Alice可能拿的大的可能拿的小的，算出来的期望值为1.25x>x，所以肯定换

运行数据：执行用时：2277MS，内存消耗：13972K

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int test = sc.nextInt();

        while (test-- > 0) {
            if (sc.nextDouble() <= 1) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！