题目描述
找出一个三元组满足：
-
为自然数，且
确保答案唯一
思路
这一题我想到了一个比较巧妙的类似二分逼近的思路
抛开限制条件1，我们可以首先考虑的情况
此时 ，此时
必然都是无理数
记这个无理数为 ，记
因此我们可以得到一个范围：最终答案中的 的平方一定在区间
内
得到这个范围我想到了一种处理方式，那就是枚举
从 时开始枚举，因为在此之前我们得到了
时的范围
很明显，唯一满足，且夹在这两个二元组中的二元组就是
得到 之后，我们判断它是否满足条件，满足则直接跳出循环
否则更新范围为 或者
，继续循环
之后的循环跟上述 的情况是类似的，这样我们就在 O(n) 的时间内解决了这题
总结
这个解法用到了一些动态规划和二分逼近的思想
我们将解空间按照 的值进行了划分，根据之前求到的
的解范围
，可以得到
的一个解范围的边界
，再根据
的大小直接返回答案（满足条件时）或是得到新的范围继续循环
代码
#include <cstdio>
#include <cmath>
int cmp(int a, int b) {
int c1 = a * a + b * b;
int c2 = (1000 - a - b) * (1000 - a - b);
return c1 - c2;
}
int main() {
int a = 1000 / (2 + sqrt(2)), b = a;
while (true) {
if (cmp(a, b) == 0) break;
b++;
if (cmp(a, b) > 0) a--, b--;
}
int c = 1000 - a - b;
printf("%d %d %d\n", a, b, c);
printf("%d\n", a * b * c);
return 0;
}
