首页 > 代码库 > Codeforces 730B：Minimum and Maximum（交互式问题）
Codeforces 730B：Minimum and Maximum（交互式问题）
http://codeforces.com/problemset/problem/730/B
题意：一个交互式问题，给出一个n代表有n个数字，你可以问下标为x和y的数的大小，会给出">"，"<"或"="，要求询问次数不能超过 
，最后输出最小的数和最大的数的下标。
思路：很新奇的题目。先将两两比较整理出一个max数组和min数组，这个时候前后较大的一个会在max数组中，较小的会在min数组中，这个时候询问了n/2次。接着我们只要对每个组进行比较，因为较大的已经在max数组里面了，我们只要递推求得较大的，同理，也可以递推求得较小的。最后的答案就是最后的组了。
记得每次printf之后要fflush(stdout)。
1 #include <bits/stdc++.h> 2 using namespace std; 3 int ma[55], mi[55]; 4 5 int main() { 6 int t; 7 scanf("%d", &t); 8 while(t--) { 9 int n;10 scanf("%d", &n);11 char s[3]; int cnt = 0;12 for(int i = 1; i < n; i += 2, cnt++) {13 printf("? %d %d\n", i, i + 1);14 fflush(stdout);15 scanf("%s", s);16 if(s[0] == ‘>‘) ma[cnt] = i, mi[cnt] = i + 1;17 else ma[cnt] = i + 1, mi[cnt] = i;18 }19 if(n & 1) { ma[cnt] = n, mi[cnt] = n; cnt++; }20 for(int i = 1; i < cnt; i++) {21 printf("? %d %d\n", ma[i-1], ma[i]);22 fflush(stdout);23 scanf("%s", s);24 if(s[0] == ‘>‘) ma[i] = ma[i-1];25 printf("? %d %d\n", mi[i-1], mi[i]);26 fflush(stdout);27 scanf("%s", s);28 if(s[0] == ‘<‘) mi[i] = mi[i-1];29 }30 printf("! %d %d\n", mi[cnt-1], ma[cnt-1]);31 fflush(stdout);32 }33 return 0;34 }
Codeforces 730B：Minimum and Maximum（交互式问题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。