题目:二分
来源:牛客网
题意
你猜一个数,裁判回答你这个数是大了还是小了还是猜对了。但是裁判都傻得很,不知道自己说的对没对,让你求裁判最多有多少个回答是正确的。
简而言之就是裁判在瞎说大小,让你求裁判最多说对了几次。
看到题目是二分你可不要被二分给迷惑了,我反正想了半天也没想出来用怎么用二分写这个题。我来说一下我的思路:
首先你说了一个数a,总共有三种情况:
- 裁判说数大了,那么裁判说对的取值范围是(-∞,a]
- 裁判说数小了,那么裁判说对的取值范围是[a,+∞)
- 裁判说数一样,那么裁判说对的取值范围是[a,a]
那么我们只需要求最大有多少个区间重叠了就行,类似于第一节课讲解的种树一题。同学们仔细去复习一遍吧。
解法
差分、离散化都行,下面给出我的代码,就是把种树的代码改了一点点而已:
#include <bits/stdc++.h> using namespace std; #define foru(i, a, b) for(auto i=(a);i<(b);++i) #define ford(i, a, b) for(auto i=(a);i>(b);--i) #define maxn 100005 typedef long long ll; inline int read() { char ch = getchar(); int f = 1, x = 0; while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); return f * x; } struct position{ int value; bool is_left; bool operator < (const position& p){ if(value == p.value) // 若两个数一样大,则左端点在前 return is_left > p.is_left; return value < p.value; } }pos[maxn << 1]; int main() { int n = read(), num, c; foru(i,0,n) { scanf("%d %c", &num, &c); if (c == '.') { pos[i << 1].value = num; pos[(i << 1) + 1].value = num; } else if (c == '+') { pos[i << 1].value = INT_MIN; pos[(i << 1) + 1].value = num - 1; } else { pos[i << 1].value = num + 1; pos[(i << 1) + 1].value = INT_MAX; } pos[i << 1].is_left = true; //左端点 pos[(i << 1) + 1].is_left = false; //右端点 } sort(pos,pos + (n << 1)); //把区间端点从小到大排序 int cover = 0, ans = 0; //cover表示区间重叠的数量 foru(i,0,n << 1){ if(pos[i].is_left) cover++; else cover--; ans = max(ans, cover); } cout << ans; return 0; }