---

E. Scuza（二分）

原创 已于 2023-08-12 02:08:52 修改 · 粉丝可见 · 202 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132241114

题目：

cobol<br/>3<br/>4 5<br/>1 2 1 5<br/>1 2 4 9 10<br/>2 2<br/>1 1<br/>0 1<br/>3 1<br/>1000000000 1000000000 1000000000<br/>1000000000<br/>

cobol<br/>1 4 4 9 9 <br/>0 2 <br/>3000000000 <br/>

思路：

这里是，二分的题目，题目的意思是有一个数组a 是阶梯高度，数组 b 是Tim 可以跨上阶梯的高度，问Tim对应的可跨上阶梯的总 最高的 高度是多少,也有一点贪心思想

这里我们 需要记录每个台阶相应位置的 总高度， 也就是求出 前缀和 ，之后我们还要存储好到达所对应高度坐标中的  Tim 所需要的跨越高度是多少,并记录到满足该条件后对应的前缀和下标是多少。

因为我们往后都是需要前面要满足的高度，也就是说 我们后面的要到达后面的阶梯高度，需要满足前面阶梯Tim跨越的高度。

所以我们可以得到对应的单调性质，通过二分查找最后一个大于或者等于 Tim 的跨越高度即可

这里还要注意用 long long

代码详解如下：

#include <iostream>
#include <vector>
#include <unordered_map>
#define endl '\n'
#define int long long
#define umap unordered_map
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
int n, m;

inline int to_Find(vector<int> &v, int &x)
{
	int l = 0, r = n - 1;
	while (l < r)
	{
		int mid = l + r + 1 >> 1;
		
		if (v[mid] <= x)
			l = mid;
		else
			r = mid - 1;
	}
	return v[l];
}

inline void solve()
{
	umap<int, int>r;		// 记录对应跨越高度的坐标

	vector<int>sum;		// 对应坐标高度前缀和

	vector<int>v;	// 实际到达该坐标所需的跨越高度
	int maxs = -1;	// maxs 为满足跨越高度的探针

	cin >> n >> m;
	for (int i = 0, x; i < n; ++i)
	{
		cin >> x;
		maxs = max(maxs, x);		// 更新探针

		// 计算前缀和
		if (!i) sum.emplace_back(x);
		else sum.emplace_back(sum.back() + x);

		// 记录对应跨越高度
		v.emplace_back(maxs);

		// 记录对应跨越高度的下标
		// 即可对应其满足的前缀和
		r[maxs] = i;
	}

	for (int i = 0, x; i < m; ++i)
	{
		cin >> x;

		// 如果连第一个台阶都不能跨越
		// 那么高度就是 0
		if (x < v[0])
		{
			cout << 0 << ' ';
			continue;
		}

		// 二分查找最后一个满足 跨越高度 是多少
		int pos = to_Find(v, x);

		// 输出满足的答案
		cout << sum[r[pos]] << ' ';
	}
	cout << endl;
}

signed main()
{
	___G;
	int _t;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}

最后提交：