P6716 [CCO2018] Gradient Descent
UMS2
·
·
题解
题目描述
一个大小为 R \times C 的棋盘上有 n 个棋子，每次询问 (x,y) 的返回值为 \sum(|x_i-x|+|y_i-y|)。至多询问 k 次，求最小的返回值。
### 思路
#### 60pts
注意到在 $x$ 轴上移动并不会改变 $y$ 轴上的总距离，反之亦然。而绝对值函数的和是一个不严格的单谷函数。故尝试在 $x$ 轴和 $y$ 轴上分别三分。
这样的询问最大次数为 $4\log_{\frac{3}{2}}10^7 \approx 160$ 。而前 40pts 只有一半的询问次数，共 60pts。
```cpp
int l=1,r=m;
while(l<r){
int lmid=l+(r-l)/3,rmid=r-(r-l)/3;
if(ask(1,lmid)<ask(1,rmid))r=rmid-1;
else l=lmid+1;
}
resy=l;
l=1,r=n;
while(l<r){
int lmid=l+(r-l)/3,rmid=r-(r-l)/3;
if(ask(lmid,resy)<ask(rmid,resy))r=rmid-1;
else l=lmid+1;
}
resx=l;
ans=ask(resx,resy);
cout<<"! "<<ans;
```
#### 80pts
注意到我们没有必要使用三分，由于本题函数是离散的，我们可以使用二分，这样的询问最大次数为 $4\log_210^7\approx 94$。
```cpp
int l=1,r=m;
while(l<r){
int mid=l+r>>1;
int lmid=mid,rmid=min(mid+1,m);
if(ask(1,lmid)<ask(1,rmid))r=rmid-1;
else l=lmid+1;
}
resy=l;
l=1,r=n;
while(l<r){
int mid=l+r>>1;
int lmid=mid,rmid=min(mid+1,n);
if(ask(lmid,resy)<ask(rmid,resy))r=rmid-1;
else l=lmid+1;
}
resx=l;
ans=ask(resx,resy);
cout<<"! "<<ans;
```
#### 100pts
注意到我们二分时并不需要关心另一个轴上的位置，于是可以一起二分，共用一个点。这样可以做到 $3\log_210^7 \approx 70$ 次询问，足以通过本题。
```cpp
int l=1,r=m,nl=1,nr=n;
while(l<r||nl<nr){
int amid=l<r?l+r>>1:1,bmid=nl<nr?nl+nr>>1:1;
int nans=ask(bmid,amid);
if(l<r){
if(nans<ask(bmid,amid+1))r=amid;
else l=amid+1;
}
if(nl<nr){
if(nans<ask(bmid+1,amid))nr=bmid;
else nl=bmid+1;
}
}
resx=nl,resy=l;
ans=ask(resx,resy);
cout<<"! "<<ans;
```