(附带讲解upper_bound函数)NOI Online#2 T1未了endless（C++，贪心+二分）

程序员文章站 2024-03-17 16:38:46

...

题目

（洛谷里有，不过是民间数据）

题目链接

思路

思路其实很简单，我们要——

透过现象看本质

第i个魔法的本质其实就是什么呢？第i个魔法的本质是将主人公所要走的距离增加a[i]，所以，我们顺理成章地想出来一个思路，大体框架就此出现——

优先选择 a[i] 较大的魔法；如果不能满足条件，就选次大的；还不能满足条件，就选第三大的……就这样一直选下去，直到满足条件或全都选完了（也就是输出 -1 ）为止。

但是如果每次对比都要再算一遍，那就太麻烦了，所以我用一个 double 型的 check[] 数组将其存储起来，check[i] 表示的就是运用前 i 大的魔法之后猪脚要用的时间。

为了更快，我们~~变本加厉地~~ 利用二分思路，以找出大于询问 t[i] 的最小 check[] ，用 upper_bound() 函数实现，代码后讲解。

以下是代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
long long n, len, v, a[N];
long long q, ans;
double check[N];

bool cmp(int a, int b) {
	return a > b;
}

void work() {
	check[0] = (double)len / (double)v;
	for(int i = 1; i <= n; ++ i) {
		check[i] = check[i-1] + ((double)a[i] / (double)v);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> len >> v;
	for(int i = 1; i <= n; ++ i) cin >> a[i];
	sort(a+1, a+1+n, cmp);
	work(); // 将所有的check[]算出
	cin >> q;
	for(int i = 1; i <= q; ++ i) {
		long long t;
		cin >> t;
		if(check[n] > t)
		cout << upper_bound(check, check+1+n, t) - (check) << endl;
		else cout << -1 << endl;
	}
	return 0;
}