专栏首页木又AI帮【leetcode刷题】T182-两地调度

【leetcode刷题】T182-两地调度


【题目】

公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0],飞往 B 市的费用为 costs[i][1]。

返回将每个人都飞到某座城市的最低费用,要求每个城市都有 N 人抵达。

示例:
输入:[[10,20],[30,200],[400,50],[30,20]]
输出:110
解释:
第一个人去 A 市,费用为 10。
第二个人去 A 市,费用为 30。
第三个人去 B 市,费用为 50。
第四个人去 B 市,费用为 20。
最低总费用为 10 + 30 + 50 + 20 = 110,每个城市都有一半的人在面试。

提示: 1 <= costs.length <= 100 costs.length 为偶数 1 <= costs[i][0], costs[i][1] <= 1000

【思路】

每个人都可以选择任意一个目的地,那么可以都先选择A市,求得总费用,再更改一部分人的目的地,即计算所有的额外费用=B市费用-A市费用,排序并且选择最小的N个,将额外费用加入到总费用中。

【代码】

python版本

class Solution(object):
    def twoCitySchedCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        res = sum(map(lambda x: x[0], costs))
        res += sum(sorted(map(lambda x: x[1] - x[0], costs))[:len(costs) // 2])
        return res

C++版本

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int res = 0;
        vector<int> tmp;
        for(int i=0; i<costs.size(); i++){
            res += costs[i][0];
            tmp.push_back(costs[i][1] - costs[i][0]);
        }
        sort(tmp.begin(), tmp.end());
        for(int i=0; i<costs.size()/2; i++)
            res += tmp[i];
        return res;
    }
};

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打卡群2刷题总结1004——无重复字符的最长子串

    https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

    木又AI帮
  • 打卡群刷题总结0803——复原IP地址

    木又AI帮
  • 【leetcode刷题】20T3-无重复字符的最长子串

    https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

    木又AI帮
  • LintCode 房屋染色题目代码

    这里有n个房子在一列直线上,现在我们需要给房屋染色,分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同,你需要设计一种染色方案使得相邻的房屋颜色不同,并且费用...

    desperate633
  • 继续学习Shell脚本(详细)

    只需要在一个定义过的变量前面加上美元符号 $ 就可以了, 另外,对于变量的{} 是可以选择的, 它的目的为帮助解释器识别变量的边界.

    心跳包
  • 90后CTO创业史,如何从校园象牙塔走向新三板?

    今天,场主想和大家聊聊爱范儿CTO兼知晓云负责人何世友,一位拥有着近8年创业经验的90后。

    养码场
  • C++ 条件变量(condition_variable)

           先贴一个condition_variable的讲解:https://en.cppreference.com/w/cpp/thread/condit...

    Ch_Zaqdt
  • java.net.ConnectException: Call From slaver1/192.168.19.128 to slaver1:8020 failed on connection exc

    1:练习spark的时候,操作大概如我读取hdfs上面的文件,然后spark懒加载以后,我读取详细信息出现如下所示的错误,错误虽然不大,我感觉有必要记录一下,因...

    别先生
  • Matplotlib新手上路(上)

    matplotlib是python里用于绘图的专用包,功能十分强大。下面介绍一些最基本的用法: 一、最基本的划线 先来一个简单的示例,代码如下,已经加了注释: ...

    菩提树下的杨过
  • Subplot和Subplots绘制子图

    plot可以绘出精美的图形,但是如果想要在一张图中展示多个子图,plot就很难办了。

    慕白

扫码关注云+社区

领取腾讯云代金券