米尔科和斯拉夫科正在打一场新的比赛。再一次斯拉夫科在每一轮比赛开始时都会给米尔科两个数字A和B，两个数字都小于100。米尔科随后必须为斯拉夫科解决以下任务：如何将所有给定的A数与所有给定的B数配对，以便这些配对的最大和尽可能小。 换句话说，如果在前几轮比赛中斯拉夫科给出了a1，a2，a3…an和b1，b2，b3…bn，确定n对（ai，bj），使所有和ai+bj的最大值最小 输入格式: 第一行输入包含一个整数N（1≤N≤100000），表示回合数。 接下来的N行包含两个整数A和B（1≤ A、B≤ 100），表示米尔科和斯拉夫科在那一轮给出的数字。 输出格式: 输出由N行组成，每轮一行。每一行输出当目前回合为止的ai+bj的最大值的最小值，用c++实现

可以使用二分答案加贪心的思想来解决这个问题。

具体来说，我们可以将所有的 A 数组和 B 数组分别排序，然后将两个数组中最大的数相加得到一个上限值，将这个上限值作为二分答案的右端点，0 作为左端点。

在二分答案的过程中，我们可以使用贪心的思想来确定是否存在一种方案使得所有和 ai+bj 的最大值不超过当前的二分值。具体来说，我们可以从大到小枚举 A 数组中的数，然后对于每个 A[i]，在 B 数组中找到最大的 j 使得 A[i]+B[j] 不超过当前二分值。如果找不到这样的 j，那么说明当前二分值太小，需要将二分答案的右端点向左移动；否则，将 B[j] 标记为已匹配，继续枚举 A 数组中的下一个数，直到所有的 A 数组中的数都被匹配完成。

如果所有的 A 数组中的数都能够被匹配完成，那么说明当前的二分值可行，我们可以尝试将二分答案的右端点向左移动；否则，说明当前的二分值太小，需要将二分答案的左端点向右移动。

最终，当二分答案的左端点和右端点相同时，这个值就是所有和 ai+bj 的最大值尽可能小的方案。

以下是 C++ 实现代码：

相关问题

米尔科和斯拉夫科正在打一场新的比赛。再一次斯拉夫科在每一轮比赛开始时都会给米尔科两个数字A和B，两个数字都小于100。米尔科随后必须为斯拉夫科解决以下任务：如何将所有给定的A数与所有给定的B数配对，以便这些配对的最大和尽可能小。 换句话说，如果在前几轮比赛中斯拉夫科给出了a1，a2，a3…an和b1，b2，b3…bn，确定n对（ai，bj），使所有和ai+bj的最大值最小

这是一个经典的问题，可以使用二分答案加贪心的思想来解决。

首先，我们可以将所有的 A 数组和 B 数组分别排序，然后将两个数组中最大的数相加得到一个上限值，将这个上限值作为二分答案的右端点，0 作为左端点。

在二分答案的过程中，我们可以使用贪心的思想来确定是否存在一种方案使得所有和 ai+bj 的最大值不超过当前的二分值。具体来说，我们可以从大到小枚举 A 数组中的数，然后对于每个 A[i]，在 B 数组中找到最大的 j 使得 A[i]+B[j] 不超过当前二分值。如果找不到这样的 j，那么说明当前二分值太小，需要将二分答案的右端点向左移动；否则，将 B[j] 标记为已匹配，继续枚举 A 数组中的下一个数，直到所有的 A 数组中的数都被匹配完成。

如果所有的 A 数组中的数都能够被匹配完成，那么说明当前的二分值可行，我们可以尝试将二分答案的右端点向左移动；否则，说明当前的二分值太小，需要将二分答案的左端点向右移动。

最终，当二分答案的左端点和右端点相同时，这个值就是所有和 ai+bj 的最大值尽可能小的方案。

C++代码解决动态规划问题尽管她在第二项任务中看到兹文科偷走了米尔科的微处理器，但米尔科的妹妹伊万娜没有告诉米尔科，因为她喜欢兹文科。她建议他一起去看电影，这样她就可以“忘记”这件事了。 Zvonko不太关心女孩，因为女孩会占用他平时花在练习数学上的宝贵时间。他建议他们两人玩一场游戏，如果伊万娜赢了，他们将一起去看电影。伊万娜同意了，她擅长跳绳，有时甚至和她的两个兄弟踢足球。 Zvonko将N个正整数放在地板上的一个圆圈内，并解释了规则： •第一个玩家接受任何数字。 •第二名玩家从与第一名玩家相邻的两个数字中选择一个。 •下一个玩家在到目前为止所取的任何数字旁边取一个数字，依此类推，直到数字用完。选择更多奇数（不能被2整除）的玩家获胜。 兹文科发挥得最好；他总是寻找一种能带来一定胜利或平局的策略。兹文科不知道伊万娜打得有多好。作为一名真正的骑士，他让伊万娜拥有了第一步。但伊万娜只在乎在大屏幕前坐在兹文科旁边，所以她寻求帮助。 编写一个程序，找出伊万娜能做出多少不同的第一步，这样她就有机会在之后获胜。

这是一个经典的博弈问题，可以使用动态规划来解决。我们定义dp[i][j][k]表示当前轮到第i个玩家，圆圈上的数字范围是[j,k]时，该玩家可以获得的最大奇数和。如果当前轮到伊万娜，则最终的结果是dp[1][1][N]，如果这个值大于N/2，则伊万娜有机会获胜。

转移方程如下：

dp[i][j][k] = max(
nums[j] % 2 == 1 ? nums[j] + dp[i%2+1][j+1][k] : dp[i%2+1][j+1][k],
nums[k] % 2 == 1 ? nums[k] + dp[i%2+1][j][k-1] : dp[i%2+1][j][k-1]
)

其中，nums是圆圈上的数字序列。

初始状态为dp[i][j][j] = nums[j] % 2 == 1 ? nums[j] : 0，表示只有一个数字时的情况。

最终的答案是对于所有的j，k，如果dp[1][j][k]大于N/2，则伊万娜有机会获胜。

以下是C++代码实现：