二分答案二分搜索专题

题目大意：
给你一个长度为 $n$n的字符串，只包含 $a或者b$a或者b，现在你可以将 $a$a换成 $b，k$b，k次，或 $b$b换成 $a$a，问你换完后最长的只有包含一个字符的子串长度是多少。
思路：
先求一下，字符 $a$a和字符 $b$b的前缀和，然后枚举起点，二分终点位置。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
char s[maxn];
int a[maxn],b[maxn];
void solved(){
	int n,k;cin>>n>>k;
	scanf("%s",s + 1);
	for(int i = 1; i <= n; i++){
		if(s[i] == 'a'){
			a[i] = a[i - 1] + 1;b[i] = b[i - 1];
		}else{
			b[i] = b[i - 1] + 1;a[i] = a[i - 1];
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		int l = i,r = n;
		while(l <= r){
			int mid = l + r >> 1;
			if(a[mid] - a[i - 1] <= k || b[mid] - b[i - 1] <= k){
				ans = max(ans,mid - i + 1);l = mid + 1; 
			}else{
				r = mid - 1;
			}
		}
	}
	cout<<ans<<endl;
}
int main(){
	solved();
	return 0;
} 

题目大意：
给你 $n$n个数，要你找到最多有多少对满足 ∣ai−aj∣<=k的二元组。
思路：
先排序，然后暴力枚举前面 $n/2$n/2个点，然后二分出第一个大于等于 $ai+z$ai+z的数，并且这个数字没有与其他数配对，所以就是一个lower_bound加一个条件 $!vis\left[mid\right]$!vis[mid]即可。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long int ll;
ll a[maxn],n,z;
bool vis[maxn];
void solved(){
	cin>>n>>z;
	for(int i = 1; i <= n; i++)cin>>a[i];
	sort(a + 1, a + 1 + n);
	a[n + 1] = 1e18;
	ll ans = 0;
	for(int i = 1; i <= n/2; i++){
		ll v = a[i] + z;
		int l = 1,r = n + 1;
		int pos = 0;
		while(l <= r){
			int mid = l + r >> 1;
			if(a[mid] >= v && !vis[mid])pos = mid,r = mid - 1;
			else l = mid + 1;
		} 
		if(pos == n + 1)continue;
		ans ++;
		vis[i] = true;
		vis[pos] = true;
	}
	cout<<ans<<endl;
}
int main(){
	solved();
	return 0;
} 

题目大意：
在一个 $1\ast n$1∗n的矩形中，有个人要放 $k$k的长度为 $a$a的小矩形到里面来，然后现在有 $m$m的询问，每个询问是问 $xi$xi是否放了小矩形，那个人说假话，老是说假话，问你最少根据多少个询问知道那个人说假话。
思路：
询问越多，那么人说假话的可能性越大，满足单调性，所以可以考虑二分答案，二分mid次数就行了。要注意的是那个人放小矩阵相邻的也不能放，就是至少两个矩形要多一个空出来，(一开始漏了这个条件浪费了好多时间)。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long int ll;
int a[maxn],m,n,k,len;
bool check(int mid){
	int last = 0;
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		if(a[i] >= 0 && a[i] <= mid){
			cnt += (i - last)/(len + 1);
			last = i;
		}
	}
	cnt += (n - last + 1) / (len + 1);
	return cnt < k;
}
void solved(){
	cin>>n>>k>>len;
	cin>>m;
	for(int i = 1; i <= n ;i ++)a[i] = -1;
	for(int i = 1; i <= m; i++){
		int x;cin>>x;a[x] = i;
	}
	a[n + 1] = 0;a[0] = 0;
	//for(int i = 1; i <= n + 1; i ++)cout<<a[i]<<" ";cout<<endl;
	int ans = -1;
	int l = 1,r = m;
	while(l <= r){
		int mid = l + r >> 1;
		if(check(mid)){
			ans = mid;
			r = mid - 1;
		}else{
			l = mid + 1;
		}
	}
	cout<<ans<<endl;
}
int main(){
	solved();
	return 0;
}

题目大意：给你一个长度为 $n$n的序列，要你找出一个最长的不超过 $k$k个不同元素的子序列。
思路：
可以发现随着你选择的子序列长度越长，它作为答案的可能性就越低，呈现单调性，所以我们可以考虑二分答案，二分mid为长度，不过check的时候需要用数据结果去重，大概复杂度是 $O\left(logn\right)$O(logn)，总的时间为 $O\left(nloglogn\right)$O(nloglogn)注意到 $n=5e5$n=5e5，所以会超时，网上看到有用莫队艹过去的，这里的正解应该是尺取法，时间复杂度 $O\left(n\right)$O(n)，枚举一个起点，然后用一个变量去测量。。一旦超过 $k$k马上退出检测答案，然后继续。这里需要用 $cnt$cnt计数，总的思路不难。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
int a[maxn],cnt[maxn];
void solved(){
	int n,k;scanf("%d%d",&n,&k);
	for(int i = 1; i <= n; i++)scanf("%d",a + i);
	int cur = 0;
	int p = 1;
	int l = -1,r = -1;
	for(int i = 1; i <= n; i++){
		while(p <= n){
			if(++cnt[a[p]] == 1)cur++;
			if(cur > k){
				if(--cnt[a[p]] == 0)cur--;
				break;
			}
			p++;
		}
		if(p - i > r - l){
			r = p - 1;l = i;
		}
		if(--cnt[a[i]] == 0)cur--;
	}
	cout<<l<<" "<<r<<endl;
}
int main(){
	solved();
	return 0;
} 

题目大意：
现在你要做蛋糕，蛋糕需要 $n$n个材料，做蛋糕需要 $ai$ai种材料，你有 $bi$bi种材料，并且你还有 $k$k个魔法粉，这 $k$k个魔法粉可以充当任意材料。问你最多可以做多少个蛋糕。
思路：
很显然的二分答案，二分蛋糕数，check检查一下满不满足。不过有个地方卡了乘法，所以需要小小的优化一下，提前计算出你拥有材料的总数，如果你拥有所有材料再加上魔法粉的材料小于需要的所有材料的和的mid倍，显然不能制作，直接返回 $false$false。
代码：

#include<bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
const int maxn = 1e5 + 10;
ll a[maxn],b[maxn],n;
ll s1 ,s2;
bool check(ll mid,ll k){
	if(mid != 0 && s1 > (s2 + k)/mid)return false; 
	for(ll i = 1; i <= n; i++){
		if(b[i] / a[i] < mid){
			k -=(long long)(mid * a[i]) - b[i];
			if(k < 0)return false;
		}
	}
	return k >= 0;
}
void solved(){
	ll k;cin>>n>>k;
	for(ll i = 1; i <= n; i++)cin>>a[i],s1+=a[i];
	for(ll i = 1; i <= n; i++)cin>>b[i],s2+=b[i];
	ll l = 0, r = 1e18 + 10;
	ll ans = 0;
	while(l <= r){
		ll mid = l + r >> 1;
		if(check(mid,k)){
			ans = mid;
			l = mid + 1;
		}else{
			r = mid - 1;
		}
	}
	cout<<ans<<endl;
}
int main(){
	solved();
	return 0;
} 

题目大意：
给你一个 $n+1$n+1的格子，你要从 $0$0到 $n+1$n+1，但是有些格子上面可能有陷阱 $li,ri,di$li,ri,di，分别表示陷阱的位置，拆除这个陷阱的位置，这个陷阱的危险级别，然后你有 $k$k士兵，每个士兵都有这个灵敏度 $ai$ai，当你这个士兵灵敏度大于陷阱危险级别可以直接走过去，如果低于的话，你的士兵就会死，现在你每走一步要花费 $1s$1s的时间，问你在花的时间不超过 $t$t秒最多可以带多少个士兵到 $n+1$n+1。
思路：
你带的士兵越多，花的时间越多，呈单调性，考虑二分士兵的人数。这里需要预处理一下士兵灵敏度，因为每次带的都是灵敏度高的去，取这几个高的中的 $min$min与陷阱级别对比。
当你士兵低于陷阱灵敏度，要先到 $ri$ri拆掉这个陷阱然后再过去，这里会有一个问题，我是先把所有的陷阱全部拆掉再回去带士兵过去，还是拆到某个带士兵走到某个位置继续拆？当下一个位置的炸弹的拆除位置在你的前，肯定是先带士兵到炸弹，然后你再去拆掉这个炸弹继续走，所以这里是先带士兵过来会比全部拆掉再带士兵过去更优，但是我们可以发现，我们走的步数不会超过 $2(n+1)+n+1$2(n+1)+n+1，我们考虑把有交集的炸弹一次性拆掉，然后直接走过去，那么有交集的地区会计算两次，涉及区间修改考虑差分。
总结：这个题目还是有一定难度，难就难在怎么带士兵走更优这里，这里的差分用的很巧妙，直接解决了这个问题。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const ll maxn = 2e5 + 10;
struct node{
	ll l,r,d;
	node(){}
	node(ll a,ll b,ll c):l(a),r(b),d(c){}
}traps[maxn];
ll m,n,k,t;
ll a[maxn];
ll di[maxn];
bool cmp(ll a,ll b){
	return a > b;
}
bool check(ll mid,ll v){
	ll cnt = 0;
	for(int i = 1; i <= n; i++)di[i] = 0;
	for(ll i = 1; i <= k; i++){
		if(traps[i].d > v){
			di[traps[i].l]++;
			di[traps[i].r + 1]--;
		}
	}
	for(int i = 1; i <= n + 1; i ++){
		di[i] = di[i - 1] + di[i];
	}
	for(int i = 1; i <= n + 1; i++){
		if(di[i] >= 1)cnt++;
	}
	cnt *= 2;
	cnt += n + 1;
	return cnt <= t;
}
void solved(){
	cin>>m>>n>>k>>t;
	for(ll i = 1; i <= m; i++)cin>>a[i];
	for(ll i = 1; i <= k; i++){
		cin>>traps[i].l>>traps[i].r>>traps[i].d;
	}
	sort(a + 1,a + 1 + m,cmp);
	ll l = 1,r = m;
	ll ans = 0;
	while(l <= r){
		ll mid = l + r >> 1;
		if(check(mid,a[mid])){
			ans = mid;
			l = mid + 1;
		}else{
			r = mid - 1;
		}
	}
	cout<<ans<<endl;
}
int main(){
	solved();
	return 0;
}