1 solutions

  • 1
    @ 2024-10-5 23:35:16

    我转了一圈,竟然没人发题解?

    那行吧,我来发

    主要思想:(没有贪心模拟

    我们来看看最关键的点:如何才能确定怎么才能钓到最多的鱼?

    方法很简单,就是一个个去试,试到更好的就选更好的 大家是不是都在往贪心上想?所以才忽略了这种方法?

    但是就纯纯这样模拟的话,恐怕会TE,甚至WA,所以还要一点点剪枝。

    也很简单,时间不够跳出就行。 (如果肆意让时光流逝,就可能会导致鱼量变成负数或者直接死循环)

    好了,讲了这么多,附上代码(有详细注释)

    #include <bits/stdc++.h>
    #define SIZE 1000
    using namespace std;
    
    struct fish
    {
    	int a,b,c,d;
    };
    
    fish fisher[SIZE];
    int n,h;
    
    int main()
    {
    	cin >> n >> h;
    	h *= 12;//这里乘以12而不是60是为了规避5分钟带来的影响
    	for(int i = 1;i <= n;i++) cin >> fisher[i].a;//每个湖第一个5分钟能钓到鱼的数量
    	for(int i = 1;i <= n;i++) cin >> fisher[i].b;//以后的每5分钟钓鱼数量比前一个 5 分钟钓鱼数量减少的数量
    	for(int i = 1;i < n;i++)  cin >> fisher[i].c;//由第i个湖到第i+1个湖所需要的时间
    	//特别注明:fisher[i].d表示这个湖第i个5分钟能钓到的鱼数
    	int sum = 0,ans = -1,maxn,H,l;
    	for(int i = 1;i <= n;i++)
    	{
    		for(int j = 1;j <= i;j++) fisher[j].d = fisher[j].a;
    		h -= fisher[i - 1].c;//要去到这个湖,先要花掉时间
    		H = h;if(h < 0) break;/*如果时间不够,就跳出*/sum = 0;
    		while(H--)
    		{
    			maxn = 0;
    			for(int k = 1;k <= i;k++)
    			{
    				if(maxn < fisher[k].d)
    				{
    					l = k;
    					maxn = fisher[k].d;
    				}
    			}
    			sum += maxn;//sum将所有能钓到的鱼的最大值全部统计到一起
    			fisher[l].d -= fisher[l].b;//更新fisher[i].d
    		}
    		ans = max(ans,sum);//先考虑去了这个湖,再看能不能钓到更多的鱼
    	}
    	cout << ans << endl;
    	return 0;
    }
    

    后语:希望能有神犇们发一些时间复杂度低一点的代码

    • 1

    Information

    ID
    10
    Time
    1000ms
    Memory
    512MiB
    Difficulty
    9
    Tags
    # Submissions
    215
    Accepted
    10
    Uploaded By