自动搬运

查看原文

来自洛谷，原作者为

	irris Good Luck.

搬运于2025-08-24 22:46:29，当前版本为作者最后更新于2023-06-03 22:20:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Preface

【管理员】你说得对，但是 2023/5/27 21:20:06
TAOI-1 也没见人考证啊。

【管理员】iRrrrrrrrrrrrris 2023/5/27 21:20:11


【管理员】iRrrrrrrrrrrrris 2023/5/27 21:20:14
椎名真昼

【管理员】iRrrrrrrrrrrrris 2023/5/27 21:20:18
这都写到脸上了

【管理员】iRrrrrrrrrrrrris 2023/5/27 21:20:21
考证 nm 呢

【管理员】iRrrrrrrrrrrrris 2023/5/27 21:20:32
剩下的全是歌曲

【管理员】你说得对，但是 2023/5/27 21:20:33
T3 没写到脸上！

【管理员】你说得对，但是 2023/5/27 21:20:35
别的确实！

フォニイ。

Solution

入门级交互题，为啥出题人一开始只出了 $\sout{k = n - 1}$ 捏 。

一个很自然的想法是由于假花和其它花美丽度之差最小为 $2v - v = v$，而其它花之间最大为 $v - 1$，所以可以打擂台找出来假花。

但是每次比较 $\bm{a, b}$ 和 $\bm{a, c}$ 是很浪费的。更优雅的想法是每次比较 $a, b$ 和 $c, d$，这样一定能同时排除 $a, b$ 或 $c, d$ 中的一方。

重复直到 $n = 3$，如果一开始是偶数导致排除到了 $n = 2$ 随便拉一朵花进来变成 $n = 3$。手玩即可 $2$ 次解决这里的 bound issues。

Code

这里提供一个比较简洁的写法。

#include <bits/stdc++.h>

void solve() {
	int N, K, b, v; std::cin >> N >> K;
	for (int i = 1, x; i < N; i += 2) {
		std::cout << "? " << i << ' ' << i + 1 << std::endl, std::cin >> x;
		if (i == 1 || x > v) b = i, v = x;
	}
	int t = (b == N - 1 ? 1 : N), x1, x2;
	std::cout << "? " << t << ' ' << b << std::endl, std::cin >> x1;
	std::cout << "? " << t << ' ' << b + 1 << std::endl, std::cin >> x2;
	std::cout << "! " << ((N & 1) && (x1 > v && x2 > v) ? N : x1 > x2 ? b : b + 1) << std::endl;
}

int main() {
	int T; std::cin >> T;
	while (T--) solve();
	return 0;
}