跳转至

算法笔记

BISHI26 构造C的歪

w3903771/algorithm

BISHI26　构造C的歪¶

入门通过率 73.62%python3样例通过牛客 AC数论

牛客原题　源码

讲解章节：构造

一句话

给 a、b，求 c 使 {a,b,c} 排序后成等差数列。

解题思路¶

这题考什么¶

等差数列的判定条件：三个数排序后 x <= y <= z 满足 x + z = 2y。给定两个数，第三个数有三种放法：放最小、放中间、放最大。

放最大：c = 2*max(a,b) - min(a,b)，序列是 min, max, c，公差 max-min；
放最小：c = 2*min(a,b) - max(a,b)，可能是负数；
放中间：c = (a+b)/2，只在 a+b 为偶数时可行。

三种放法不一定都可行（放中间要求 a+b 是偶数，放最小可能得到负数），但「放最大」对任意 a、b 都成立，而且 2*max - min >= max >= 1 一定是正数。本解法就固定选这一种，一行算式出答案，不必分情况讨论。

数据规模与复杂度¶

a,b <= 1e6，单组数据，O(1)。答案量级最大 2e6，Python 不用担心溢出。

坑在哪¶

a == b 时 c = 2a - a = a，三个数全相等，公差 0 的等差数列，合法；
答案不唯一：第三个数放最小、放中间、放最大都可能构成等差数列，题面的两个样例就对同一组输入 (3, 2) 分别给出了 1 和 4。因此本地不能拿标准答案逐字符比对，要用 special judge（特殊评测程序，按题目条件验证选手输出是否合法，而不是比对字面）：本题配了 solutions/_spj/BISHI26.py，它把 a、b、c 排序后检查 x + z == 2y；
用 (a+b)//2 会在 a+b 为奇数时错，别偷懒。

参考实现¶

solutions/BISHI26.py
import sys

a, b = map(int, sys.stdin.buffer.read().split()[:2])
# 把 c 放在最大处：min, max, 2*max-min 是公差为 max-min 的等差数列
print(2 * max(a, b) - min(a, b))