稻花乡里说丰年,听取蛙声一片
查看原帖
稻花乡里说丰年,听取蛙声一片
777911
hansen121楼主2024/9/15 16:50
#include <bits/stdc++.h>
using namespace std;
int n,p,s;
struct node
{
	int w,v;
}a[1000001];
bool cmp(node aa,node bb)
{
	return aa.v<bb.v;
}
int f[1000001];
int check(int V)
{
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++)
	{
		for(int j=V;j>=a[i].w;j--)
		{
			f[j]=max(f[j],f[j-a[i].w]+a[i].v);
		}
	}
	if (V==6) cout<<f[V]<<endl;
	return f[V]>=p;
}
int main()
{
	cin>>n>>p>>s;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].w>>a[i].v;
	}
	sort(a+1,a+n+1,cmp);
	int l=0,r=1000,mid;
	while(l<=r)
	{
		mid=(l+r)/2;
		if (check(mid)) r=mid-1;
		else l=mid+1;
	}
	if (l>10000) cout<<"NO";
	else cout<<r;
	return 0;
} 

求各位大佬帮忙调一下,谢谢。

2024/9/15 16:50
加载中...