自动搬运

查看原文

来自洛谷，原作者为

	Cutest_Junior 平平淡淡才是真

搬运于2025-08-24 22:28:50，当前版本为作者最后更新于2021-02-10 21:49:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解 P7329 【[w33z-2018] Dream and More Discs】

题意

• 阴间交互题；
• 有 $n$ 类音乐盘，每类有 $2^m-1$ 片按重要度递增排序的音乐盘，所有盘重要度互不相同；
• 每次可以询问第 $i$ 类第 $j$ 个盘的重要度，求所有盘中重要度第 $k$ 小的是哪个盘；
• $n\le50$，$m\le11$，询问次数不超过 $1111$ 次，重要度都是不超过 $10^{18}$ 的正整数。

做法

记 $a_{i,j}$ 为第 $i$ 类第 $j$ 个盘的重要度。

对每个区间二分，若当前 $\sum\limits_{i=1}^{n}mid_i>k$，就可以找到 $p$ 满足 $a_{p,mid_p}>a_{i,mid_i}(1\le i\le n,i\ne p)$，把 $r_p$ 改为 $mid_p-1$，也就是说，原来从 $mid_p$ 到 $r_p$ 的这段区间的盘都不用考虑了。想一想，为什么。

根据上面的定义，比 $a_{p,mid_p}$ 小的至少有 $\left(\sum\limits_{i=1}^{n}mid_i\right)-1$（不包括它本身，所以要减一）个盘，而 $k<\sum\limits_{i=1}^{n}mid_i$，说明第 $k$ 个盘的重要度一定小于 $a_{p,mid_p}$。

同理，若当前 $\sum\limits_{i=1}^{n}mid_i\le k$，则可以找到 $p$ 满足 $a_{p,mid_p}<a_{i,mid_i}(1\le i\le n,i\ne p)$，把 $l_p$ 改为 $mid_p+1$。

可以发现每一类最多查询 $m$ 次，总查询次数 $O(nm)$。

十年 OI 一场空，不开 long long 见祖宗。

我才不会告诉你我因为没开 long long 连 WA 12 次。

代码

#include <cstdio>

using namespace std;

typedef long long ll;

const int N = 55;

int l[N], r[N], mid[N];
ll ans[N];

void in(int x, int y) {
	printf("? %d %d\n", x, y);
	fflush(stdout);
	scanf("%lld", &ans[x]);
}

int main() {
	int n, m, k, th;
	scanf("%d%d%d%d", &n, &m, &k, &th);
	for (int i = 1; i <= n; ++i) {
		l[i] = 1, r[i] = (1 << m) - 1;
		mid[i] = (l[i] + r[i]) >> 1;
		in(i, mid[i]);
	}
//	printf("%d %d\n", mid[1], mid[2]);
	for (int i = 1; i <= n * m; ++i) {
		int minn = 1, maxx = 1;
		int cnt = mid[1];
		for (int j = 2; j <= n; ++j) {
			cnt += mid[j];
			if (l[j] > r[j]) {
				continue;
			}
			if (l[minn] > r[minn]) {
				minn = j;
			}
			if (l[maxx] > r[maxx]) {
				maxx = j;
			}
			if (ans[j] < ans[minn]) {
				minn = j;
			}
			if (ans[j] > ans[maxx]) {
				maxx = j;
			}
		}
//		printf("cnt %d\n", cnt);
		if (k < cnt) {
			r[maxx] = mid[maxx] - 1;
			mid[maxx] = (l[maxx] + r[maxx]) >> 1;
			if (l[maxx] <= r[maxx]) {
				in(maxx, mid[maxx]);
			}
		}
		else {
			l[minn] = mid[minn] + 1;
			mid[minn] = (l[minn] + r[minn]) >> 1;
			if (l[minn] <= r[minn]) {
				in(minn, mid[minn]);
			}
		}
		if (i == n * m) {
			printf("! %d %d", minn, mid[minn]);
			return 0;
		}
	}
}