T3 - ^_^ 还是 :-( 题目链接跳转：点击跳转 > 一道简单的思维题目，难度定在【普及-】还算是合理的。不过 USACO 的 Bronze 组别特别喜欢考这种类似的思维题目。 普通算法 考虑采用贪心的思路，先把序列按照从大到小的原则排序。暴力枚举一个节点 iii，判断是否有可能满足选择前 iii 个数字 −1-1−1，剩下的数字都至少 +1+1+1 的情况下所有的数字都大于零。 那么该如何快速的判断是否所有的数字都大于零呢？首先可以肯定的是，后 n−in - in−i 个数字一定是大于零的，因为这些数字只会增加不会减少。所以我们把重点放在前 iii 个数字上面。由于数组已经是有序的，因此如果第 iii 个数字是大于 111 的，那么前 iii 个数字在减去 111 之后也一定是正整数。 由于使用了排序算法，本算法的单次查询时间复杂度在 O(Nlog⁡2N)O(N \log_2 N)O(Nlog2 N) 级别，总时间复杂度为 O(N2log⁡2N)O(N^2 \log_2 N)O(N2log2 N)，可以在 1s\tt{1s}1s 内通过所有的测试点。 本题的 C++ 代码如下： 本题的 Python 代码如下： 二分答案优化 注意到答案是单调的，因此可以使用二分答案的算法来适当优化。虽然效果微乎其微，但在整体时间运行上表现良好。 优化后的 C++ 代码如下： 优化后的 Python 算法如下：

题意 给出正整数数组 AAA, 问是否存与 AAA 长度相等且各项皆为正整数的数组 BBB 使得 AAA 的各项元素之和等于 BBB 的各项元素之和且 A、BA、BA、B 数组的每组对应项不同。 解析 记 A、BA、BA、B 数组的第 iii 项分别为 Ai,BiA_i,B_iAi ,Bi ，又记 A、BA、BA、B 数组的各项之和为 SA、SBS_A、S_BSA 、** ，根据题意，Ai≠BiA_i\ne B_iAi =Bi 且 SA=SBS_A= S_BSA =** 我们遍历 AAA 的每一项以对 BiB_iBi 估计下界。若 Ai≠1A_i\ne 1Ai =1，则 BiB_iBi 可取到 111；而当 Ai=1A_i=1Ai =1 时，根据 Ai≠BiA_i\ne B_iAi =Bi ，可得 Bi≠1B_i\ne 1Bi =1，于是 Bi≥2B_i\ge2Bi ≥2, 因此若记 AAA 数组中有 ppp 个 111 和 qqq 个非 111 元素，则： **≥2p+q⇔SA≥2p+qS_B\ge 2p+q\Leftrightarrow S_A\ge 2p+q ** ≥2p+q⇔SA ≥2p+q 因此我们只要计算出 SAS_ASA 和 2p+q2p+q2p+q 即可判断 BBB 是否存在. 复杂度分析 对每个测试点，只需要遍历一次 AAA 数组，因此复杂度为 O(Tn)O(Tn)O(Tn) 代码