https://www.luogu.org/problemnew/show/P2370
二分+背包
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <ctime> using namespace std; #define LL long long #define mod int(1e9+7) struct ahah { int moon,val; } a[1006]; bool cmp(ahah a,ahah b) { return a.moon<b.moon; } int n,dp[1006],s,p; bool check(int x) { memset(dp,0,sizeof(dp)); for(int i=1; i<=n; i++) { if(a[i].moon>x)break; for(int j=s; j>=a[i].moon; j--) { dp[j]=max(dp[j],dp[j-a[i].moon]+a[i].val); } } // cout<<x<<" "; // for(int i=1;i<=n;i++)cout<<dp[i]<<" ";cout<<" "; if(dp[s]>=p)return 1; else return 0; } int main() { scanf("%d%d%d",&n,&p,&s); for(int i=1; i<=n; i++)scanf("%d%d",&a[i].moon,&a[i].val); sort(a+1,a+1+n,cmp); int l=1,r=n,ans=-1; while(l<=r) { int mid=(l+r)/2; if(check(a[mid].moon)) { r=mid-1; ans=a[mid].moon; } else l=mid+1; } if(ans==-1)printf("No Solution!"); else printf("%d",ans); }