百度之星2020---1003.Permutation

Problem Description 一开始有 n个数,他们按 1…n的顺序排列,要求交换最多 m对数字(同一个数字可以参与多次交换),使得逆序对数目最大。 对于一个序列 A,如果存在正整数 i, j使得1≤i<j≤n 而且 A[i] > A[j],则 <A[i],A[j]> 这个有序对称为 A的一个逆序对。 Input 第一行一个正整数test (1≤test≤100000) 表示数据组数。 对于每组数据,一行两个整数 n,m (1≤n≤1000000,0≤m≤1000000) 表示数字个数和最多可以交换的数字对数。

百度之星2020---1002.Game

Problem Description Alice 和 Bob 在玩游戏。 桌面上有两堆金币,少的那堆有 x 个金币,多的那堆有 2x 个金币。 假设金币可以被无限细分。Alice 和 Bob 事先都不知道 x是几,但是他们都知道 x是一个 (0, 1]之间均匀分布的随机实数。 Alice 会等概率的被分配到其中的一堆金币,Bob 会得到另一堆。x的值和两堆金币的分配是相互独立的。 拿到金币以后,Alice 会马上数清自己拿到多少金币。然后 Alice 可以选择是否和 Bob 那堆换。 给定 Alice 拿到的金币数目,请问 Alice 要不要交换,使得她期望能得到的金币数目更多? 如果交换期望得到的金币数目多于不交换期望得到的金币数目,输出交换,否则不交换。 Input 第一行一个正整数test (1≤test≤200000) 表示数据组数。 接下来每行一个小数p(0<p≤2),p最多保留五位小数,表示 Alice 拿到的金币数目。

百度之星2020---1001.Discount

Problem Description 学皇来到了一个餐馆吃饭。他觉得这家餐馆很好吃,于是就想办个会员。 一共有 n种会员充值卡套餐,假设学皇这餐饭的消费为 a元,选择第 i种套餐,需要充值 b[i] * a 的钱,这次吃饭可以打 c[i]×10 折,由充值的钱支付(即这次吃饭只需要从充值金额中扣除 a×c[i] 元)。以后用剩余的充值的钱吃饭不再打折。 请问学皇应该选择哪个套餐(必须选择恰好一个套餐),使得优惠的比例最大? 优惠比例的定义是把充的钱用完以后,(本来应该付的钱 - 实际付的钱) / 本来应该付的钱。在这个题目里,实际付的钱就是这次充值的花费。