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

const int N = 1e5 + 10;
int a[N], t;

int bs1(int l, int r) // 返回  >= t 最小值，查找的是左边界
{
	while (l < r)
	{
		int mid = (l+r)/2;
		if (a[mid] < t) l = mid + 1;
		else r = mid;
	}
	return l;
}

int bs2(int l, int r) // 返回  <= t 最大值，查找的是右边界
{
	while (l < r)
	{
		int mid = (l+r+1)/2;
		if (a[mid] > t) r = mid-1;
		else l = mid;
	}
	return l;
}

int main()
{
	int n, q;
	cin >> n >> q;
	for(int i = 0; i < n; i++) cin >> a[i];
	
	while (q--)
	{
		cin >> t;
		int lt = bs1(0, n-1);
		int rt = bs2(0, n-1);
		if (a[lt] == t)
			cout << lt << " " << rt << endl;
		else
			cout << "-1 -1" << endl;
	}
	
	return 0;
}

例题：不太甜的糖果

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

const int N = 3e5;
int a[N], s[N], n, m;


bool check(int i, int mid)
{
	int k = s[mid] - s[i-1];
	return k < m; // i~mid的甜度和 < m，更新左边界
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		s[i] = s[i-1] + a[i];  // 预处理前缀和
	}
	int ans = 3e5;
	// O(nlogn)
	for (int i = 1; i <= n; i++)  // i 遍历起点
	{
		int l = i, r = n; // l~r表示右端点的可能范围
		while (l < r) // 二分查找终点
		{
			int mid = (l+r)/2;
			if (check(i, mid)) l = mid+1;
			else r = mid;
		}
		if (s[r] - s[i-1] >= m) // 满足>=m才去更新ans
			ans = min(ans, r-i+1);
	}
	if (ans == (int)3e5) ans = 0;
	cout << ans;
	return 0;
}

例题：网线主管

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

const int N = 1e4 + 10;
int a[N], n, k, maxlen;

bool check(int mid) // 以当前mid长度作为切割长度，是否能够切出至少k条网线
{
	ll sum = 0; // 能切出多少条长度为mid的网线
	for(int i = 1; i <= n; i++)
		sum += a[i]/mid;
	return sum >= k; // 说明mid长度切出来的网线比k多，更新l
}

int main()
{
	// 枚举网线的切割长度 [100, 10000000]
	// 题目要求切出k条，且尽可能长，由大->小枚举
	cin >> n >> k;
	for (int i = 1; i <=n ; i++)
	{
		double x; cin >> x;
		a[i] = x * 100; // 转换厘米
		maxlen = max(maxlen, a[i]);
	}
	int l = 1, r = 1e8;
	while (l < r)
	{
		int mid = (l+r+1)/2;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	if (check(1)) cout << fixed << setprecision(2) << l*1.0/100;
	else cout << "0.00";
	return 0;
}

搜索——连通性问题【数池塘dfs】

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
char g[N][N];
int n, m, cnt = 0;
int dx[] = {0,1,0,-1}, dy[]={1,0,-1,0};

void dfs(int sx, int sy)
{
	g[sx][sy] = '.';
	for (int i = 0; i < 4; i++)
	{
		int nx = sx + dx[i], ny = sy + dy[i];
		if (nx>=1&&nx<=n&&ny>=1&&ny<=m&&g[nx][ny]=='W')
			dfs(nx,ny);
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> g[i][j];
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			if (g[i][j] == 'W')
			{
				dfs(i, j);
				cnt++;
			}
		}
	cout << cnt;
	
	return 0;
}