Codeforces Round 703 (Div. 2)补题
前言
一题自闭,掉大分。
题目
注意只能后移不能前移即可。
之前学长讲过一维推广到二维的情况,赛时也回想到了,但是没想到曼哈顿距离也能推广。算是个结论吧。
一维:奇数取中位数,偶数取两个中位数之间的任何位置都可以。
AC代码:
1 | /* |
交互题限制次数。1e5 20次,显然二分。
赛时炸了脑子不够清醒,在那码了删,删了码也不知道码了些啥,比赛一结束理了一下思路就知道正解了。
先查询一次[1,n],得到position
- position==1,那么最大值肯定在[2,n],对这个区间进行二分,每次查询[1,mid],如果结果不为1,那么说明最大值在[mid+1,n],否则最大值在[2,mid]
- position==n,那么最大值肯定在[1,n-1],对这个区间进行二分,每次查询[mid,n],如果结果不为n,那么说明最大值在[1,mid-1],否则最大值在[mid,n-1]
- position在[2,n-1],我们再查询一次[1,position],如果结果还是position,那么最大值在区间[1,position],我们把position看做n,按照情况二处理即可。否则把position看做1,按照情况一处理。
AC代码:
1 | /* |
打比赛时头脑还是不够清醒,得改掉这个坏习惯。