C2. Guessing the Greatest (hard version) (二分、思维)

傷城~ 2021-07-16 18:56 385阅读 0赞

[题目][Link 1]

对于easy情况的做法是，对每个范围都询问两次第二大值，借用第二大值确定最大值所在范围，然后缩小范围。

hard情况的做法是，先询问第二大值所在位置p，然后根据最大值所在其左还是右分情况进行二分，其比easy询问次数少了一半是因为每次问询都使用mid—p（假设最大值在p左边），如果第二大值位置还等于p，说明最大值位于mid—r范围内，使 l=mid,如果第二大值位置不等于p,说明最大值位置不位于mid—r范围内，使 r=mid-1，最大值在p右边的情况也类似。还要注意下不能询问范围为1的区间。

Code:

#include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    ll x[Max], y[Max];
    
    int main()
    { 
    	int l = 1, r, t=0;
    	cin >> r;
    	cout << "? 1" << " " << r << endl;
    	int p;cin >> p;
    	if (p != 1) { 
    		cout << "? 1" << " " << p << endl;
    		cin >> t;
    	}
    	if (t == p)
    	{ 
    		r = p - 1;
    		while (l < r)
    		{ 
    			int mid = (l + r + 1) / 2;
    			cout << "? "<<mid << " " << p << endl;
    			cin >> t;
    			if (t == p)l = mid;
    			else r = mid - 1;
    		}
    		cout << "! " << l << endl;
    	}
    	else
    	{ 
    		l = p + 1;
    		while (l < r)
    		{ 
    			int mid = (l + r)/2;
    			cout << "? " << p << " " << mid << endl;
    			cin >> t;
    			if (t == p) r = mid;
    			else l = mid + 1;
    		}
    		cout << "! " << l << endl;
    	}
    }

[Link 1]: https://codeforc.es/problemset/problem/1486/C2

发表评论取消回复

表情：

评论列表（有 0 条评论，385人围观）

还没有评论，来说两句吧...

相关阅读

相关【sorting】CF855div3 2. Unforgivable Curse (hard version)

[Problem - E2 - Codeforces][] 题意：给你两个长度为n的只有英文的字符串a,b，然后给你一个k，你可以使si和s(i+k)或者si和s(i+k

素颜马尾好姑娘i/ 2024年03月22日 11:41/ 0 赞/ 65 阅读

相关 @codeforces - 1209G2@ Into Blocks (hard version)

目录 @description@ @solution@ @accepted code@ @details@ --------------------

墨蓝/ 2023年06月01日 14:56/ 0 赞/ 24 阅读

相关 @codeforces - 1209E2@ Rotate Columns (hard version)

目录 @description@ @solution@ @accepted code@ @details@ --------------------

左手的ㄟ右手/ 2023年06月01日 12:57/ 0 赞/ 28 阅读

相关 codeforces C. NP-Hard Problem 二分图的判定

C. NP-Hard Problem time limit per test 2 seconds memory limit per test 256 megabytes

小鱼儿/ 2022年07月21日 01:30/ 0 赞/ 163 阅读

相关 C - Median(166C 思维+ 二分)

题目描述： A median in an array with the length of n is an element which occupies position

刺骨的言语ヽ痛彻心扉/ 2022年02月19日 10:53/ 0 赞/ 181 阅读

相关 1462E2 - Close Tuples (hard version)（组合数）

[题目][Link 1] 思路：先对数组排序，然后算出每个数的贡献，先从第一个数开始找到第一个大于它的值+k的数（二分），下表差即为可选的构成m个数元组的可选数的个数s，

不念不忘少年蓝@/ 2021年09月03日 03:53/ 0 赞/ 286 阅读

相关 C. The Hard Work of Paparazzi (dp)

[题目][Link 1] 思路：这是一道最长递增子序列的变式。 dp\[i\] 代表前i个名人中第i个名人被访问所能访问的最大名人数目先看暴力的方法，那么我

ゞ浴缸里的玫瑰/ 2021年07月17日 01:07/ 0 赞/ 302 阅读

相关 C - k-LCM (easy version AND hard version) (构造、思维)

[题目][Link 1] 思路：先来考虑k=3的情况，如果n为奇数则三个数分别为 1 n/2 n/2，这样最大是n/2。如果n为偶数，如果n%4==0，则三个数为 n/

àì夳堔傛蜴生んèń/ 2021年07月16日 21:10/ 0 赞/ 362 阅读

相关 Guess The Numbe (交互题)

D. Guess The Number Time limit 2 seconds Memory limit 512Mb Input standard inpu

左手的ㄟ右手/ 2021年07月16日 20:23/ 0 赞/ 307 阅读

相关 C2. Guessing the Greatest (hard version) (二分、思维)

[题目][Link 1] 对于easy情况的做法是，对每个范围都询问两次第二大值，借用第二大值确定最大值所在范围，然后缩小范围。 hard情况的做法是，先询问第二大

傷城~/ 2021年07月16日 18:56/ 0 赞/ 386 阅读