鏈接： C. Searching Local Minimum
題意： 給你一個大小為 n 排列 , 一次詢問可以得到位置 i 的數，要求在不超過 100 次詢問的條件下找到該排列的一個波谷，即找到位置 k滿足：a[k] < a[k - 1] && a[k] < a[k + 1]，
思路：
- 我們先假設 a[1]小于 a[n] , 因為已經保證了 a[0] 為 無窮大，所以可以保證 a[0] 已經大于 a[1] , 對于 1 到 n 這一部分，如果他保持單調遞增或者 是 先增后減 那么答案就是 1 如果保持單調遞減那么答案就是 n. 如果是先減后增那么答案就是那個波谷，所以我們可以證明 答案一定是存在的（當然如果 a[1] 大于 a[n]，那么答案同理也是存在的），
- 所以我們可以利用以上性質，假設存在一個區間 【l , r】，a[l] < a[r],并且 a[l-1] > a[l].那么在 l 到 r 內一定有解，所以我們只需要一直維護這樣一個區間 ，并且通過二分不斷縮小區間，那么最后一定能得到解，
- 最后考慮怎么一直維持一個這樣的區間 ， 讓 mid = (l + r）/ 2,如過 a[l] < a[mid] ，那么就可以讓 r = mid, 此時這個區間[l + 1,mid]仍滿足上述條件，如果 a[l] > a[mid] ,那么我們考慮 mid - 1,如果 a[mid - 1] > a[mid],那么 [mid , r] 滿足條件，否則的話我們就必須反向考慮 [l , mid - 1] ,也是滿足的（注意這里是反向找，就相當于 一 開始 a[1] > a[n]) 具體可以看代碼理解（用了flag表示方向），
代碼：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e6 + 7;
const int mod = 1e9 + 7;
int T;
int n,a[maxn],vis[maxn];
void query(int x){
if(vis[x]) return ;
printf ("? %d\n",x);
fflush(stdout);
scanf("%d",&a[x]);
vis[x] = 1;
}
int main (){
int l,r,mid;
a[0] = a[n + 1] = n + 1;
scanf("%d",&n);
if(n == 1){
printf ("! 1\n");
return 0;
}
query(1);
query(n);
int flag = 1;
if(a[1] > a[n]) flag = 0;
l = 1,r = n;
while(l <= r){
if(flag){
query(l + 1);
if(a[l] < a[l + 1]){
printf ("! %d\n",l);
return 0;
}
mid = (l + r) / 2;
query(mid);
if(a[mid] > a[l]){
r = mid;
l += 1;
}
else{
query(mid - 1);
if(a[mid - 1] > a[mid]){
l = mid;
}
else {
r = mid - 1;
flag = 1 - flag;
}
}
}
else{
query(r - 1);
if(a[r] < a[r - 1]){
printf ("! %d\n",r);
return 0;
}
mid = (l + r) / 2;
query(mid);
if(a[mid] > a[r]){
l = mid;
r -= 1;
}
else{
query(mid + 1);
if(a[mid + 1] > a[mid]){
r = mid;
}
else {
l = mid + 1;
flag = 1 - flag;
}
}
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/258060.html
標籤：其他
上一篇：作為過來人的我是如何寫博客的？