AtCoder入门练习题B--题解报告
https://practice.contest.atcoder.jp/tasks/practice_2
这里有三组测试用例。
第一组N = 26, Q = 1000。因为N * N < Q,所以可用冒泡排序法。具体代码参考官方给的Sample Code。
第二组N = 26, Q = 100,由于询问次数只有100次,可用插入排序法处理。每插入一个数据前,先用二分查找法查找插入的位置,这样可提升排序速度。但是这样需要询问26log226次,还是不能通过所有的数据。这就要求我们需要对每一次询问的答案做一个记忆化处理,记录下小球的质量关系,然后根据这个质量关系就可以得出有序的数列,从而降低时间复杂度。
第三组N=5, Q=7。先比较第0个和第1个,第2个和第3个,第1个和第3个,再求第5个的位置,最后求第2个和第0个、第1个、第5个的位置关系。
#include<bits/stdc++.h> using namespace std; char s[29], ans[29]; int cmp['Z'+5]['Z'+5]; int cnt = 0; // 比较两个字符,如果a>b返回true,如果a<b返回false bool cmp_char(const char a, const char b) { char cp; if(cmp[a][b] == -1) { printf("? %c %c ", 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; } } return cmp[a][b]; } // N为5时,调用此方法进行排序 void sort_N5(char c) { if(cmp_char(c, s[1])) { if(cmp_char(c, s[2])) { s[3] = c; } else { s[3] = s[2]; s[2] = c; } } else { if(cmp_char(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; } } } // N为26时,调用此方法进行排序 void sort_N26(char c) { int l = 0, r = cnt; while(l < r) { int mid = (l + r) >> 1; if(cmp_char(c, ans[mid])) { l = mid + 1; } else { r = mid; } } cnt++; // 在新加入的c比原先的所有字符都大时,if条件成立 // 比如原先的顺序为"AB",新加和的"C"比"B"大,即"AB"变为"ABC"时 if(cmp_char(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] = '