ZigZagK的博客
[二分]Codeforces1479A【Searching Local Minimum】题解
ZigZagK
2021年2月8日 02:54
Codeforces
查看标签

题目概述

CF1479A

解题报告

如果 $a_i<a_{i+1}$ 则称 $i$ 为上点，否则称 $i$ 为下点。

首先如果 $1$ 是上点，或者 $n-1$ 是下点，那么 $1$ 或 $n-1$ 就是局部最小值。

如果 $L$ 是下点，$R$ 是上点，那么 $[L+1,R]$ 里一定有局部最小值。因此想到二分，如果二分的点 $mid$ 是下点，就将 $mid$ 赋给 $L$ ，否则 $mid$ 赋给 $R$ 。

刚开始 $L=1,R=n-1$ ，最终当 $L+1=R$ 时，$R$ 就是局部最小值。

示例程序

#include<cstdio>
#include<cstdlib>
using namespace std;

int n,L,R;

void Print(int x) {printf("! %d\n",x);fflush(stdout);exit(0);}
int Ask(int i,int j){ //-1:i<i+1 1:i>i+1
    int A;printf("? %d\n",i);fflush(stdout);scanf("%d",&A);
    int B;printf("? %d\n",j);fflush(stdout);scanf("%d",&B);
    return A>B?1:-1;
}
int main(){
    scanf("%d",&n);
    if (n==1) Print(1);
    if (Ask(1,2)<0) Print(1);
    if (Ask(n-1,n)>0) Print(n);
    int L=1,R=n-1;
    for (int mid=L+(R-L>>1);L+1<R;mid=L+(R-L>>1))
        Ask(mid,mid+1)>0?L=mid:R=mid;
    Print(R);return 0;
}
版权声明：本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处！