首页给出了a1,a2,a3…an和b1,b2,b3…bn,确定n对(ai,bj),使所有和ai+bj的最大值最小.第一行输入包含一个整数N(1≤N≤100000),表示回合数。接下来的N行包含两个整数A和B(1≤ A、B≤ 100),表示每一轮给出

给出了a1,a2,a3…an和b1,b2,b3…bn,确定n对(ai,bj),使所有和ai+bj的最大值最小.第一行输入包含一个整数N(1≤N≤100000),表示回合数。接下来的N行包含两个整数A和B(1≤ A、B≤ 100),表示每一轮给出

时间: 2024-04-05 11:29:57 浏览: 87

我们第一行包括两个整数n,k(1<=n<=100,k<=6e5),表示有n个数字,目标和为k 第二行输入n个整数(c1 c2

某一天齐木楠雄和照桥心美又在一起玩找数字的游戏,游戏规则是这样的,桌子上有n个的卡片，每一张卡片上都有一个数字(划重点，这里没有说明每个数字必须独一无二),心美从中选择三次(可以重复选择同一张卡片),然后得到一个数为三张卡片上数字之和,如果卡片上的数字之和恰好为k,那么心美获胜,否则齐神获胜。如果心美获胜了，齐神只能乖乖的听从心美的要求说出"哦呼"了。心美从桌上随机选了三张牌（每一张卡片被心美照顾的概率相同）。燃堂想要知道齐木说出哦呼的概率有多大，因为如果齐神说了"哦呼"，那么可能今天就不能和哥们一起吃拉面了。输入描述: 对于每一个案例,我们第一行包括两个整数n,k(1<=n<=100,k<=6e5),表示有n个数字,目标和为k。第二行输入n个整数(c1 c2...cn),(1<=ci<=2e5),表示每一张卡片上的数字。输出描述: 输出一个形为a/b的最简分数,表示齐神说出"哦呼"的几率的概率(如果概率为0,输出0/1)。

这是一个经典的二分答案问题。我们可以二分答案mid，然后检查是否存在一种方案使得所有的(ai+bj)<=mid。具体的，我们可以对a数组进行排序，然后枚举b数组中的每个元素，用二分法在a数组中找到最大的不超过mid-bj的数，这个数的下标就是对应的ai。如果找不到这样的数，说明mid太小了，否则说明mid可以取得更小的值。具体代码实现如下：

阅读全文