博客主页 🏗️
wy的leetcode刷题记录_Day69
wy的leetcode刷题记录_Day69

Author:

wy-1226

©

Wordage:

共计 1487 字

needs:

约 1 分钟

Popular:

259 ℃

Created:

目 录

wy的leetcode刷题记录_Day68

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间:2023-6-7

前言

@TOC

2611. 老鼠和奶酪

2611. 老鼠和奶酪

题目介绍

有两只老鼠和 n 块不同类型的奶酪,每块奶酪都只能被其中一只老鼠吃掉。

下标为 i 处的奶酪被吃掉的得分为:

如果第一只老鼠吃掉,则得分为 reward1[i] 。
如果第二只老鼠吃掉,则得分为 reward2[i] 。
给你一个正整数数组 reward1 ,一个正整数数组 reward2 ,和一个非负整数 k 。

请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下,最大得分为多少。

示例 1:
输入:reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2 输出:15
解释:这个例子中,第一只老鼠吃掉第 2 和 3 块奶酪(下标从 0 开始),第二只老鼠吃掉第 0 和 1 块奶酪。 总得分为 4 + 4 +
3 + 4 = 15 。 15 是最高得分。
示例 2:

输入:reward1 = [1,1], reward2 = [1,1], k = 2 输出:2 解释:这个例子中,第一只老鼠吃掉第 0 和
1 块奶酪(下标从 0 开始),第二只老鼠不吃任何奶酪。 总得分为 1 + 1 = 2 。 2 是最高得分。

思路

简单的贪心+模拟:
新建立一个数组reward3用来记录reward1和reward2的差,我们假设老鼠2吃完了所有的奶酪,但是此时要求老鼠1也需要吃k个并得分最大,这时我们将reward3对应的加入reward2就是reward1中的值,那么我们只需要将reward3中最大的k个加入reward2中即可。

代码

class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        int n=reward1.size();
        vector<int> reward3(n);
        int ans=0;

        for(int i=0;i<n;i++)
        {
            ans+=reward2[i];
            reward3[i]=reward1[i]-reward2[i];
        }
        sort(reward3.begin(),reward3.end(),greater<int>());

        for(int i=0;i<k;i++)
        {
            ans+=reward3[i];
        }

        return ans;
    }
};

收获

简单的贪心+模拟

文章二维码
wy的leetcode刷题记录_Day69
共计 0 条评论,点此发表评论
博客主页 wyのblog I know you are here. 百度统计
鄂ICP备2023003777号-1 本站已运行 324 天 13 小时 12 分 自豪地使用 Typecho 建站,并搭配 MyDiary 主题 Copyright © 2023 ~ 2024. wyのblog All rights reserved.
打赏图
打赏博主
欢迎
搜 索
足 迹
分 类
  • 默认分类
  • Code
  • 日记
  • 音乐
  • 游戏
  • 阅读
  • 计划
  • 图片
  • 旅游
  • 影视