当前位置:网站首页>Tianchi online programming arranges interview city (greedy)

Tianchi online programming arranges interview city (greedy)

2020-12-06 15:49:54 Michael Amin

1. subject

source :https://tianchi.aliyun.com/oj/210874425247820050/215397455965131520

There are N Interviewers need to be interviewed , The company arranged two cities for the interview A and B, Every interviewer has come to A The cost of the city costA And to B The cost of the city costB.

The company needs to divide the interviewers into two groups , bring total cost Minimum .

N It's even 
2<=N<=1e5
 The answer is sure to be in int Within the scope of 
1<=costA,costB <=1e6

explain
It is required that the number to go to A is equal to the number to go to B

 Example 
 Input : cost = [[5,4],[3,6],[1,8],[3,9]]
 Output : 14
 explain :  The first and the second go to B City , Go to the rest A City 

2. Problem solving

  • The difference is small A City
class Solution {
    
public:
    /**
     * @param cost: The cost of each interviewer
     * @return: The total cost of all the interviewers.
     */
    int TotalCost(vector<vector<int>> &cost) {
    
        // write your code here
        sort(cost.begin(), cost.end(),[&](auto &a, auto &b){
    
            return a[0]-a[1] < b[0]-b[1];//  The difference is small A City 
        });
        int sum = 0;
        for(int i = 0; i < cost.size(); ++i)
        {
    
            if(i < cost.size()/2)
                sum += cost[i][0];//  The difference is small A City 
            else
                sum += cost[i][1];
        }
        return sum;
    }
};

603ms C++


my CSDN Blog address https://michael.blog.csdn.net/

Long click or sweep code pay attention to my official account (Michael amin ), Come on together 、 Learn together !
Michael amin

版权声明
本文为[Michael Amin]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201206154645139w.html