1 solutions

  • 0
    @ 2021-10-13 21:56:39

    爱吃糖的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;
    }
    
    • 1

    Information

    ID
    19
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    10
    Tags
    # Submissions
    2
    Accepted
    2
    Uploaded By