6231. 雇佣 K 位工人的总代价
题意：一个数组表示雇佣工人花费，k表示需要雇佣的人数，从数组前后各选candidates个人，从中选花费最小下标最小的工人，然后数组更新，重复上述操作，直至选到k个人。
思路：用set对数据进行存储，第一关键字是存储工人花费，第二关键字存储下标，set默认有序，第一个即为花费最小下标最小的数，然后根据下列条件更新数组。
（1）l > r,此时表明已取完数组中所有元素，不需要添加元素
（2）i < l,i表示所取的最小下标，在左边添加元素
（3）i > r,在右边添加元素
class Solution {
public:
long long totalCost(vector<int>& costs, int k, int candidates) {
long long ans = 0;
int n = costs.size(), l, r;
set<pair<int, int>>st;
for(l = 0; l < candidates; l ++) {
st.insert({costs[l], l});
}
for(r = n - 1; r >= n - candidates; r --) {
st.insert({costs[r],r});
}
while(k){
int i = st.begin()->second;
st.erase(st.begin());
ans += costs[i];
k --;
if(l > r) continue;
if(i < l){
st.insert({costs[l],l});
l ++;
}
else {
st.insert({costs[r],r});
r --;
}
}
return ans;
}
};
6232. 最小移动总距离
题意：一条直线上有n个坏的机器人，m个工厂，一个数组表示机器人所处位置，另一个数组第一关键
字表示工厂所处位置，第二关键字表示工厂所能修理机器人的数量，问修理好所有的机器人所需最小
的移动距离。
思路：dp[i][j]表示前j个机器人在前i个工厂所需的最小移动距离。
class Solution {
public:
long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
int n = robot.size();
int m = factory.size();
sort(robot.begin(), robot.end());
sort(factory.begin(), factory.end());
vector<vector<long long> >dp(m + 1, vector<long long>(n+1, 0x3f3f3f3f3f3f));
dp[0][0] = 0;
for(int i = 0; i < m; i ++) {
dp[i + 1][0] = 0;
int pos = factory[i][0];
int num = factory[i][1];
for(int j = 0; j < n; j ++) {
long long sum = 0;
long long min_cost = dp[i][j + 1];
for(int k = j; 0 <= k && j - k < num; k --) {
sum += abs(robot[k] - pos);
min_cost = min(min_cost, sum + dp[i][k]);
}
dp[i + 1][j + 1] = min_cost;
}
}
return dp[m][n];
}
};