大大大模拟

2024-01-01 06:37:17

简单来说就是答案就在题面上,题目怎么说就怎么做即可。

听起来很简单,做起来很难,很考验码力。想做大模拟的可以去试试csp的T3(一般都是大模拟),非常折磨人,动不动WA了,考验细节。

1. LC 1599 经营摩天轮的最大利润

这题纯模拟也能过,当然压缩一下更好。我纯模拟过的,常数时间很炸裂 。

维护的过程变量:

  1. 最大利润
  2. 最小轮转次数(仅当利润更大时更新,不取等于)
  3. 轮转次数
  4. 利润
  5. 摩天轮四座舱乘客数量
  6. 摩天轮首座舱(即将上乘客的座舱)
  7. 摩天轮尾座舱
  8. 剩余乘客
  9. 当前批次

遍历所有批次,当所有批次上完且rest==0时停止遍历,可枚举所有利润。

压缩的做法是首先上完所有乘客,然后看剩下的人够撑几轮的,去掉那些赚不了钱的轮次,把能赚钱的轮次加上就行了。

另外可以维护乘客数量总和,但我觉得无所谓了,O(4)也叫时间?

class Solution {
    public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
        if(boardingCost*4<=runningCost){
            return -1;
        }
        int mP = 0; // 最大利润
        int mOp = -1; // 最小轮转次数
        int op = 0;
        int P = 0; // 当前利润
        int[] cnt = new int[]{0,0,0,0};
        int si = 0; int ei = 3;
        int rest = 0;
        int bat = 0;
        while(rest>0 || bat<customers.length ){
            if(bat<customers.length){
                rest += customers[bat++];
            }
            cnt[si++]+=Math.min(4,rest); // 有人上车
            if(si==4) si=0;
            cnt[ei++] = 0; // 末班下车
            if(ei==4) ei=0;
            rest -= Math.min(4,rest); // 等待人数减少
            op++; // 操作次数增加
            // 计算收益
            P += calSum(cnt) * boardingCost - runningCost;
            if(P>mP){
                mP = P;
                mOp = op;
            }
        }
        return mOp;
    }

    private int calSum(int[] cnt){
        int sum = 0;
        for (int i : cnt) {
            sum += i;
        }
        return sum;
    }

}

文章来源:https://blog.csdn.net/lyh20021209/article/details/135321221
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。