Fork me on GitHub

[二分][思维]CF1479A

呜呜

题目连接
发现自己现在真的是个笨比这种题都不会做了…

刚开始的时候试着找权值和下标之间的关系然后找点单调性,然后发现这两者之间一点关系都没有然后就自闭了
发现题意可以转化成:找一个最短的(长度为1的区间)内存在元素$i$满足$a[l-1]>a[l]$同时$a[r]a[l]$同时$a[r]a[m+1],那么这个存在一个解的区间就会变成$[m,r]$,反之这个存在解的区间就会变成$[l,m+1]$,就这样一直二分到长度为$1$,那么这个长度为$1$的区间就是答案.
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

int n;

int main ( void ) {
scanf ( "%d" , &n );
if(n==1){
printf("! 1\n");
return 0;
}
int l=1,r=n;
while(l<=r){
int mid=(l+r)>>1;
printf("? %d\n",mid);
fflush(stdout);
int m;scanf("%d",&m);
printf("? %d\n",mid+1);
fflush(stdout);
int m1;scanf("%d",&m1);
if(m>m1)
l=mid+1;
else
r=mid;
if ( l == r ) {
fflush(stdout);
printf("! %d\n",l);
break;
}
}
return 0;
}

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:[二分][思维]CF1479A

文章作者:兮水XiShui丶

发布时间:2021年04月27日 - 13:04

最后更新:2021年04月27日 - 13:04

原始链接:http://krrrr.top/2021/04/27/二分-思维-CF1479A/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。