20分求助
查看原帖
20分求助
1841357
Lower_HeSn楼主2025/8/29 20:04
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
int n, m, p, num[MAXN], cnt, f[MAXN];
struct node {
	int u, v;
}a[MAXN];
map<int, int> mp;
bool cmp(node x, node y) {
	return x.u < y.u;
}
int main() {
	cin >> n >> p >> m;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i].u >> a[i].v;
	}
	sort(a + 1, a + n + 1, cmp);
	for(int i = 1; i <= n; i ++) {
		if(!mp[a[i].u]) {
			mp[a[i].u] = 1;
			cnt ++;
			num[cnt] = a[i].u;
		}
	}
	int l = 1, r = cnt, ans = -1;
	while(l < r) {
		int mid = (l + r) / 2;
		int lim = num[mid];
		memset(f, 0, sizeof(f));
		for(int i = 1; i <= n; i ++) {
			if(a[i].u > lim) {
				break;
			}
			for(int j = m; j >= a[i].u; j --) {
				f[j] = max(f[j], f[j - a[i].u] + a[i].v);
			}
		}
		if(f[m] >= p) {
			ans = lim;
			r = mid;
		}
		l = mid + 1;
	}
	if(ans == -1) {
		cout << "No Solution!";
	}
	else {
		cout << ans;
	}
	return 0;
}

总不能是二分写错了吧?

2025/8/29 20:04
加载中...