爱吃糖的dumpline题解

这道题的核心思路就是二分查找答案，因为单颗糖的最多就在1000，所以直接1——1000范围内二分check就行了 check就一个简单的01背包板子，但是加一个判断条件当当前这课糖的时间高于这个时间就跳过 如果在1000以内找到了答案直接输出否则就不行，输出dumpline很伤心！

#include<iostream>
#include<queue>
#include<algorithm>
#include<string.h>
#define PII pair<int,string>
#include<math.h>
#include<vector>
#include<map> 
using namespace std;
typedef long long ll; 
const int N=1e6+5;
int h[N],t[N]; 
int dp[N];
int n,p,S;
bool check(int k)
{
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
{	
if(t[i]>k)continue;//当时间大于k的时候就跳过，不参与。
	for(int j=p;j>=t[i];j--)
	{
		dp[j]=max(dp[j],dp[j-t[i]]+h[i]);
	}
}	
return dp[p]>=S;
}
int main(){

cin>>n>>S>>p;
for(int i=0;i<n;i++)
{
cin>>t[i]>>h[i];
}
int l=1,r=1000;
int mid;
mid=(l+r)>>1;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) r=mid-1;
else l=mid+1; 
}
if(l<=1000)cout<<l<<"\n";
else cout<<"dumpline很伤心!\n";
return 0;
}