自动搬运

查看原文

来自洛谷，原作者为

	CuFeO4 予我最狂热的孤独

搬运于2025-08-24 22:25:48，当前版本为作者最后更新于2025-02-14 17:01:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

非常有意思的一道题。注意 $q$ 是不变的。

允许的查询次数比较小，考虑二分。由于知道了速度 $q$ 也无法知道位置，但知道了位置可以反推出速度 $q$ 的范围，而且可以证明 $q$ 可能的取值范围一直在缩小，从而考虑二分询问位置 $x$。

具体的，假如当前询问为 $[l_{k},r_{k}]$，那么最快的速度 $v_{max}$ 就是 $\max\limits_{1\le i<k}(r_k-l_i)/(k-i)$，最慢的速度 $v_{min}$ 就是 $\min\limits_{1\le i<k}(l_k-r_i)/(k-i)$，然后左右端点 $l=l_{k}+v_{min}$，$r=r_{k+1}+v_{max}$。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
  //auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
  auto I = stdin,O = stdout;
#else
  auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
int p,v,L[101],R[101],t;
auto Q = [](int l,int r){cout<<"check "<<l<<' '<<r<<endl;string s;cin>>s;return (s[0] == 'Y');};
signed main(){
  cin.tie(nullptr)->sync_with_stdio(false);
  cin>>p>>v;
  int l = 0,r = p,lv = 0,rv = v;
  while(l < r){
    int mid = (l + r) >> 1;
    if(Q(l,mid)) r = mid;
    else l = mid + 1;
    for(int i = 0;i < t; ++i) 
      lv = max(lv,(l-R[i])/(t-i)),
      rv = min(rv,(r-L[i])/(t-i));
    L[t] = l,R[t] = r;
    l += lv,r += rv;
    t++;
  }
  cout<<"answer "<<l<<endl;
}