B Antiamuny wants to leaern binary search again

原创于 2023-09-09 14:00:01 发布 · 粉丝可见 · 205 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132776712

题目：

C/C++:

int f(int l,int r,int x) { // l <= x <= r
    int cnt = 0;
    while(l <= r) {
        cnt++;
        int mid = (l + r) / 2;
        if (mid == x) break;
        if (mid < x) l = mid + 1;
        else r = mid - 1;
    }
    return cnt;
}

样例：

`cobol<br/>5<br/>3 7 2<br/>6 12 2<br/>2 10 3<br/>6 14 8<br/>5 8 1<br/>`

6 11 9 -1 6

思路：

根据题意，暴力循环 l 到 r 一个样例肯定不会超时，但是这里有测试样例 t 就会导致超时，

刚好题目已经给出了二分模板，我们可以根据二分模板，二分查找 l 和 r 中是否有 x 的 cnt 循环满足我们需要找的 cnt 即可

代码详解如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;

int cnt;	// 全局定义 cnt

// 题目所给的寻找 x 二分循环次数
inline int f(int l,int r,int x) { // l <= x <= r
    int cnt = 0;
    while(l <= r) {
        cnt++;
        int mid = (l + r) >> 1;
        if (mid == x) break;
        if (mid < x) l = mid + 1;
        else r = mid - 1;
    }
    return cnt;
}

// 这里我们二分对应的 l r 寻找 x 是否有我们要找的 cnt
inline int TwoFind(int l,int r) { // l <= x <= r
    // 这里的 tl 和 tr 是存储好原来的 l r，
	// 方便 我们 寻找二分 x cnt 的次数 
    int tl = l,tr = r,F;
    
	while(l <= r) {
    	
        int mid = (l + r) >> 1;
        // F 是二分 mid 后 cnt 次数
        F = f(tl,tr,mid);
        
        // 如果 当前的 mid 二分循环 cnt 次数与我们需要找的相符合
        // 则返回结果
		if (F == cnt) return mid;
        
        // 否则继续查找
		if (F < cnt) l = mid + 1;
        else r = mid - 1;
    }
    // 如果找不到，返回 -1
    return -1;
}

inline void solve()
{
	int l,r;
	cin >> l >> r >> cnt;
	int ans = TwoFind(l,r);
	cout << ans << endl;
}


int main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}