(20929) 중간

https://www.acmicpc.net/problem/20929

단계별로 풀어보기

41단계(인터랙티브와 투 스텝 1) 10번째

 

 

 

A와 B의 x(=n/2)번째 수가 a, b라고 하자. a<b라고 하면 A의 x번째 수보다 크거나 같은 수가 a에 n-x개, b에 n-x+1개로 총 n+1개 있다. 따라서 A의 1~x번째 수는 중간값보다 작거나 같다. 같은 방식으로 생각하면 B의 x+1~n번째 수는 중간값보다 크거나 같다.

따라서 A와 B의 1~n번째 수들 중 중간값은 A의 x+1~n번째 수와 B의 1~x번째수들 중 중간값을 구하는 것과 같다. a>b면 반대로 하면 된다.

범위가 절반으로 줄어들었으므로 이분 탐색으로 계속해서 범위를 줄여나가면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  if(n==1){
    int a, b;
    cout << "? A 1" << endl;
    cin >> a;
    cout << "? B 1" << endl;
    cin >> b;
    
    cout << "! " << (a<b ? a : b);
    
    return 0;
  }
  
  int ar=1, al=n, br=1, bl=n, amid, bmid, aresp, bresp;
  
  while(true){
    amid= (ar+al)/2;
    bmid= (br+bl)/2;
    
    cout << "? A " << amid << endl;
    cin >> aresp;
    cout << "? B " << bmid << endl;
    cin >> bresp;
    
    if(ar==al) break;
    
    if(aresp<bresp){
      ar= amid+1;
      bl= bmid;
    }else{
      al= amid;
      br= bmid+1;
    }
  }
  
  cout << "! " << (aresp<bresp ? aresp : bresp);
  
  return 0;
}