这是函数交互的模板。
给了你一个函数 int Seniorious(int x)
,返回交互库内部的数与你猜的数的大小关系。你需要实现一个 int Chtholly(int n,int c)
,在不超过 c(c=20) 次内猜出交互库所想的不大于 {10}^6 的数。
这题明显是二分,但是很多人不理解交互题是怎么工作的(还有一道 IO 交互是 P1733),这里讲一下:
int Seniorious(int x)
:交互库接收到 x
之后,把 x
输出到 Special Judge,然后输入 Special Judge 返回的结果,返回这个结果。
int Chtholly(int n,int c)
:交互库调用完这个函数之后,把返回的答案输出到 Special Judge,如果正确则你拿到 AC,否则你拿到 WA。
来看看题解给的模板程序:
#include <cstdio> // 在本题中并不是必须的
extern "C" int Seniorious(int); // 在这里需要声明一次交互库给出的函数。
extern "C" int Chtholly(int n, int OvO) { // 在这里实现交互库要求你实现的函数。
int ans = 1;
for (int l = 1, r = n, mid = (l + r) >> 1; l <= r; mid = (l + r) >> 1) if (Seniorious(mid) >= 0) {
r = (ans = mid) - 1;
} else {
l = mid + 1;
}
return ans;
}
包含头文件在这里不是必须的,但如果你需要调用一些包括 std::sort
之类的函数,就要包含头文件。
要声明一下交互库给的函数(因为要兼容 C 语言,所以要加 extern "C"
前缀,部分函数交互题不用加,例如 P11818)。
最后实现要求你实现的函数(要加 extern "C"
,部分题不用加)。
这样就做完了。