Leetcode每日一题 —— 1665. 完成所有任务的最少初始能量

开发调优
,
1

思路
我一开始的思路是，按差值降序排列，优先完成差值最大的任务，然后累计实际消耗并尽可能的复用这份差值。
结果写代码的时候直接tab出来了，而且比我的思路还简单。 :rofl:
看起来思路应该是，按差值升序排列，从差额最小的任务开始累计，每次在必要能量(ans+task[0])与最低能量(task[1])中取最大值以保证本次任务能够进行。

代码

    public int minimumEffort(int[][] tasks) {
        Arrays.sort(tasks, Comparator.comparingInt(a -> (a[1] - a[0])));
        int ans = 0;
        for (int[] task : tasks) {
            ans = Math.max(ans + task[0], task[1]);
        }
        return ans;
    }
3 个赞
3

贪心题。排序方案还是很要想一下的，最开始只想到是不是用 minimum 去排，但似乎过不了。

举例试了一下才发现好像是按差值来排序。minimum-actual 这个差值实际上代表每个任务完成后至少能剩余的量，从这个角度看每次当然剩下越多越好。

class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        // 耗费的能量肯定 <= 最低能量要求，不用担心
        // 假设有 <a0, m0>, <a1, m1> 两个工作，目前能量是 E
        // - 若先完成第一个，再完成第二个，则 E>=max(m0, a0+m1)
        // - 若先完成第二个，再完成第一个，则 E>=max(m1, a1+m0)
        // 取更小的一种情况，假设第一种情况更优，则有 a0+m1 >= a1+m0
        // 则有 m1-a1 >= m0-a0
        // 因此把 minimum-actual 大的往前排，优先执行
        // 
        // 先降序排列
        sort(tasks.begin(),tasks.end(),[](const vector<int>& a,const vector<int>& b){
            if(b[1]-b[0]==a[1]-a[0]){
                // 相等的话按耗费能量排
                return a[1]>b[1];
            }
            return a[1]-a[0]>b[1]-b[0];
        });
        int res=0; 
        int remaining=0;
        for(vector<int>& t:tasks){
            if(remaining<t[1]){
                // 不满足最低能量了，补
                // 差值累加进结果
                res+=t[1]-remaining;
                remaining=t[1];
            }
            remaining-=t[0];
        }
        return res;
    }
};
4

想着hard没那么简单，开始用差值排序+二分去写了,写完发现二分没啥用。不过反正都是 n\log{n} 的。

class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        int l = -1,r = 1;
        std::sort(tasks.begin(),tasks.end(),[](const vector<int>& a, const vector<int>& b) -> bool {
            return a[1] - a[0] > b[1] - b[0];
        });
        int res = 0;
        int presum = 0;
        for(const auto &it : tasks) {
            res = max(res,it[1] + presum);
            presum += it[0];
        }
        return res;
    }
};
1 个赞
5 
impl Solution {
  pub fn minimum_effort(tasks: Vec<Vec<i32>>) -> i32 {
    let mut tasks: Vec<_> = tasks.into_iter().map(|task| (task[0], task[1])).collect();
    tasks.sort_unstable_by_key(|(a, m)| a - m);
    tasks.into_iter().rfold(0, |acc, (a, m)| m.max(acc + a))
  }
}

preprocess :: [(Int, Int)] -> UV.Vector (Int, Int)
preprocess (UV.fromList -> tasks) = runST $ UV.unsafeThaw tasks >>= liftA2 (*>) (VAI.sortBy (compare `on` uncurry (-))) UV.unsafeFreeze

minimumEffort :: [(Int, Int)] -> Int
minimumEffort (preprocess -> tasks) = go 0 (UV.length tasks - 1)
 where
  go acc i | i < 0 = acc
  go acc i = let (actual, minimum) = tasks UV.! i in go (max (acc + actual) minimum) (i - 1)

看数据量猜多半是排序之后贪心，排序策略是关键。
课上学过一个专门用来解决排序相关贪心的方法叫交换论证。
假设你有一个序列是最优的，现在考虑其中相邻项，设它们的花费是 a_1, a_2，门槛是 m_1, m_2，在这之前你用到还剩 C。
那么可以推出 C \geqslant m_1, C-a_1\geqslant m_2。
现在交换这两项，尝试推导交换后序列不变好的条件（因为假定了原来的最优）。
交换后的门槛条件为 C \geqslant m_2, C-a_2\geqslant m_1，前者是必然成立的（条件中的第二式可以推出），所以不变好的关键就是第二个不一定能成立。
也就是说不变好的充要条件为 a_2 + m_1 \geqslant a_1 + m_2，整理得到 a_1 - m_1 \leqslant a_2 - m_2。
所以排序策略就是拿实际费用减去门槛后升序排列。排好之后倒着推就能推出最小的初值。

完整的交换论证还需要证明不相邻项交换也不变好，这个可以从相邻项导出，做题只研究相邻项就够了。

1 个赞