leetcode:1029. 两地调度(中等)

题目:

leetcode:1029. 两地调度(中等)

分析:

看完题目之后,个人思路:
暴力的话就是 2的n次方 的复杂度。
然后应该就是再次基础上进行的一个剪枝吧!
然后看标签是一个贪心。
然后想了想,2N * 2个数据中,最大,最小的那个数据都有可能被选到的。最值贪心不行。

题解:

leetcode:1029. 两地调度(中等)
可以直接理解:A【i】-B【i】
或者按照题解:
全部都去A,花费sum,然后要减去(B【i】- A【i】),为去B而不去A多出来的费用,sum-n/2 个
(B【i】- A【i】),sum是一定的,然后减去的当然越小越好。

代码:

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        vector<int> v;
        int sum=0;
        for(int i=0;i<costs.size();i++)
        {
            sum+=(costs[i][0]);
            v.push_back(costs[i][0]-costs[i][1]);
        }
        sort(v.begin(),v.end());
        //cout<<v[0]<<' '<<v[1]<<' '<<v[2]<<' '<<v[3]<<' ';
        for(int i=costs.size()/2;i<costs.size();i++)
        {
            sum-=v[i];
        }
        return sum;
    }
};
上一篇:考研机试 6.手机键盘


下一篇:力扣 1029. 两地调度 Java