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)。

 #include <bits/stdc++.h>

 using namespace std;

 int ma[], mi[];

 int main() {

     int t;

     scanf("%d", &t);

     while(t--) {

         int n;

         scanf("%d", &n);

         char s[]; int cnt = ;

         for(int i = ; i < n; i += , cnt++) {

             printf("? %d %d\n", i, i + );

             fflush(stdout);

             scanf("%s", s);

             if(s[] == '>') ma[cnt] = i, mi[cnt] = i + ;

             else ma[cnt] = i + , mi[cnt] = i;

         }

         if(n & ) { ma[cnt] = n, mi[cnt] = n; cnt++; }

         for(int i = ; i < cnt; i++) {

             printf("? %d %d\n", ma[i-], ma[i]);

             fflush(stdout);

             scanf("%s", s);

             if(s[] == '>') ma[i] = ma[i-];

             printf("? %d %d\n", mi[i-], mi[i]);

             fflush(stdout);

             scanf("%s", s);

             if(s[] == '<') mi[i] = mi[i-];

         }

         printf("! %d %d\n", mi[cnt-], ma[cnt-]);

         fflush(stdout);

     }

     return ;

 }

巴特西

Codeforces 730B：Minimum and Maximum（交互式问题）

最新文章

热门文章