USC Problem A 钓鱼贪心

曾经终败给现在 2022-08-21 10:39 121阅读 0赞

题目链接：[http://61.187.179.71:9988/problem.php?cid=1104&pid=0][http_61.187.179.71_9988_problem.php_cid_1104_pid_0]

题目意思：有n个小湖序号从1到n，每个小湖每5分钟能钓到fi数量的鱼，但每过5分钟在此小湖钓到的鱼的数量就会减少di，从小湖i到i+1需要的时间为ti，不能回头，也就是不能从i+1号小湖到i号小湖，给你h小时，问最多能钓到多少鱼，最后钓鱼的人可能停到任意小湖。

解题思路：一开始还以为是简单的dp，写了写，发现复杂度爆炸还超级难写，后来发现是贪心题。。。  
我们可以枚举钓鱼人最后停到哪个小湖，直接用总时间减去到最后一个小湖的时间，这样就不用考虑走路花费的时间了。  
假设钓鱼人最后停到了小湖i，我们每次从1-i号小湖中选取可以钓到最多鱼的小湖去钓鱼，选取完之后减去相应的di，重复做这样的操作直到时间为0，得到钓鱼人最后停到小湖i时能钓到的鱼。  
最后枚举i我们便能得到结果，但如果枚举求可以钓到鱼最多的小湖会超时，所以我们要用优先队列来维护。特殊：如果钓到的鱼数量一样则优先弹出序号小的。

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <numeric>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    typedef long long LL;
    
    struct P
    {
        int val;
        int poi;
    };
    struct cmp
    {
        bool operator()(P p1,P p2)
        {
            if(p1.val==p2.val) return p1.poi>p2.poi ;
            else return p1.val<p2.val;
        }
    
    };
    priority_queue<P,vector<P>,cmp >pq;
    
    int main()
    {
        int n;
        while(RI(n)!=EOF&&n)
        {
            int h;
            RI(h);
            h=h*60;
            int f[35];
            int d[35];
            int t[35];
            for(int i=0; i<n; i++)
                RI(f[i]);
            for(int i=0; i<n; i++)
                RI(d[i]);
            for(int i=1; i<n; i++)
                RI(t[i]);
            t[0]=0;
            int ans=-1;
            int ans1[35];
            mem(ans1);
            int h1=h;
            for(int i=0; i<n; i++)
            {
                if(h1-t[i]*5<=0) break;
                else h1-=t[i]*5;
                int h2=h1,ans2=0,ans3[35];
                mem(ans3);
                P p1;
                for(int j=0; j<=i; j++)
                {
                    p1.val=f[j];
                    p1.poi=j;
                    pq.push(p1);
                }
    
                while(h2-5>=0)
                {
                    h2-=5;
                    P p2=pq.top();
                    if(p2.val<=0) break;
                    else
                    {
                        pq.pop();
                        ans2+=p2.val;
                        p2.val-=d[p2.poi];
                        ans3[p2.poi]++;
                        pq.push(p2);
    
                    }
    
                }
    
                if(ans2>ans)
                {
                    for(int i=0;i<n;i++)
                    ans1[i]=ans3[i];
                    ans=ans2;
                }
            while(!pq.empty()) pq.pop();
    
            }
    
            int summ=0;
            int endd;
    
            for(int i=0;i<n;i++)
            {
                summ+=ans1[i]*5;
                if(ans1[i]) endd=i;
            }
            summ=h-summ;
            for(int i=0;i<=endd;i++)
            {
                summ-=t[i]*5;
            }
            if(summ<0) summ=0;
            for(int i=0;i<n-1;i++)
            {
                if(i==0) cout<<ans1[i]*5+summ<<", ";
                else cout<<ans1[i]*5<<", ";
            }
    
            cout<<ans1[n-1]*5<<endl;
    
            cout<<"Number of fish expected: "<<ans<<endl;
    
            cout<<endl;
        }
    
        return 0;
    }

[http_61.187.179.71_9988_problem.php_cid_1104_pid_0]: http://61.187.179.71:9988/problem.php?cid=1104&pid=0