交互题专题

每次输出后，必须刷新标准输出：fflush(stdout);

https://atcoder.jp/contests/practice/tasks/practice_2

题意：询问q次之内完成对元素的排序。一个是对26个元素在100次之内。一个是对5个元素排序在7次之内。

分析：对于26-100的情况，我们想到用类似于插入排序的二分，每次插入的时候二分插入的位置，这样子询问比较次数是logn，但是元素移动次数单词是O(n)O(n)的，但我们只关心交互的次数，所以算法没问题。再考虑对于5—7的这个数学小问题的具体做法：

  • 7次比较完成5个元素的排序：

    ​ 有五个数字，[a, b, c, d, e]，进行排序。以下排序均按从小到大进行排序：

    • 将a与b进行排序，排序结果为[a’, b’]，共用1次比较，累计1次比较；
    • 将c与d进行排序，排序结果为[c’, d’]，共用1次比较，累计2次比较；
    • 将a’与c’进行比较，若a’ < c’，则a’ < c’ < d’，同时a’ < b’；否则 c’ < a’ < b’，同时c’ < d’。共用1次比较，累计3次比较。将未排入序列的数字记为x；
    • 将e向已排序的三个元素中进行插入，最大需2次比较，累计5次比较；
    • 将x将向序列中进行排序。由于已知x比序列序列中一个元素要大，所以x一定比当前序列中最左值要大，所以最多还要和三个元素进行比较，需要2次比较，累计7次比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;
 
char s[29], ans[29];
int cmp['Z'+5]['Z'+5];
int cnt = 0, QQ = 1;
 
bool cmp_user(const char a, const char b) {
	char cp;
	//这里使用记忆化
	if(cmp[a][b]==-1) {
		printf("? %c %c\n", a, b);
		fflush(stdout);
		scanf(" %c", &cp);
		if(cp=='>') {
			cmp[a][b] = true;
			cmp[b][a] = false;
			return true;
		}
		else {
			cmp[a][b] = false;
			cmp[b][a] = true;
			return false;
		}
	}
	else return cmp[a][b];
}
 //提前将比较函数封装起来作为一个接口，不仅可以让代码思路清晰还可以减小码量
void ins2(char c) {
	if(cmp_user(c, s[1])) {
		if(cmp_user(c, s[2])) s[3] = c;
		else s[3] = s[2], s[2] = c;
	} else {
		if(cmp_user(c, s[0])) {
			s[3] = s[2];
			s[2] = s[1];
			s[1] = c;
		} else {
			s[3] = s[2];
			s[2] = s[1];
			s[1] = s[0];
			s[0] = c;
		}
	}
}
 
void ins(char c) {
	int l = 0, r = cnt;
	while(l<r) {
		int mid = l+r>>1;
		if(cmp_user(c, ans[mid])) l = mid+1;
		else r = mid;
	}
	cnt ++;
	if(cmp_user(c, ans[r])) r ++;
	for(int i=cnt; i>=r+1; i--) ans[i] = ans[i-1];
	ans[r] = c;
}
 
int main() {
	int N, Q;
	scanf("%d%d", &N, &Q);
	
	for(int i=0; i<26; i++) s[i] = (char)(i+'A');
	s[N] = '\0';
	
	if(N==26) {
		//对于大数据我们直接二分加记忆化得方式，这里的记忆化很重要，防止重复跟系统交互
		
		memset(cmp, -1, sizeof(cmp));
		cnt = 0;
		ans[0] = s[0];
		ans[N] = '\0';
		for(int i=1; i<N; i++) ins(s[i]);
		
		printf("! %s\n", ans);
	} else {
		memset(cmp, -1, sizeof(cmp));
		if(cmp_user(s[0], s[1])) swap(s[0], s[1]);
		if(cmp_user(s[2], s[3])) swap(s[2], s[3]);
		if(cmp_user(s[1], s[3])) {
			swap(s[0], s[2]);
			swap(s[1], s[3]);
		}
		char x = s[2];
		if(cmp_user(s[4], s[1])) {
			if(cmp_user(s[4], s[3])) {
				s[2] = s[3];
				ins2(x);
			} else {
				s[2] = s[4];
				s[4] = s[3];
				ins2(x);
			}
		} else {
			if(cmp_user(s[4], s[0])) {
				s[2] = s[1];
				s[1] = s[4];
				s[4] = s[3];
				ins2(x);
			} else {
				s[2] = s[1];
				s[1] = s[0];
				s[0] = s[4];
				s[4] = s[3];
				ins2(x);
			}
		}
		printf("! %s\n", s);
	}
	//system("PAUSE");
}