社区讨论

upper_bound咋用,求助大佬

P6473[NOI Online #2 入门组] 未了参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo14flon
此快照首次捕获于
2023/10/22 15:02
2 年前
此快照最后确认于
2023/11/02 14:34
2 年前
查看原帖
用了upper_bound之后......

全错!

求调

有没有大佬能善良地帮我看一下(主要看upper_bound,当然有其他建议也虚心接受),鄙人感激不尽!

附:

本蒟蒻第一次用upper_bound,大佬轻点喷。

代码

CPP
#include <bits/stdc++.h>

using namespace std;

#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
const int N = 2e5 + 5;

int n,magic[N],q,t;
int l,v,w[N];
//double l,v,w[N];

void calculate_w () {
	w[0] = l;
//	w[0] = l / v;
	for (int i = 1;i <= n;++i)
		w[i] = w[i - 1] + magic[i];
//		w[i] = w[i - 1] + magic[i] / v;
}

int find_t (int t) {
/*
	for (int i = 0;i <= n;++i)
		if (w[i] > t)
			return i;
	return -1;
*/
	if (w[n] <= t)
		return -1;
/*
	int ans;
	int l = 0,r = n,mid;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (w[mid] > t) {
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	return ans;
*/
	return upper_bound(w,w + 1 + n,t) - w;
}

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

int main () {
	fastio;
	cin >> n >> l >> v;
	for (int i = 1;i <= n;++i)
		cin >> magic[i];
	sort(magic + 1,magic + 1 + n,cmp);
	calculate_w();
	cin >> q;
	while (q--) {
		cin >> t;
		t = t * v;
		cout << find_t(t) << "\n";
	}
/*
	for (int i = 0;i <= n;++i)
		cout << w[i] << "	";
	cout << "\n";
	for (int i = 1;i <= n;++i)
		cout << magic[i] << "	";
*/
	return 0;
}

谢谢!

回复

3 条回复,欢迎继续交流。

正在加载回复...