5984. 拆分數位後四位數字的最小和
題目描述：給你一個四位整數，讓你重排這個整數中的數字然後分成兩部分，允許有前導\(0\)。問分成的兩部分的十進制表示的和的最小值。
思路：根據題意模拟即可、
時間複雜度：\(O(1)\)
參考代碼：
class Solution {
public:
int minimumSum(int num) {
string s = to_string(num);
vector<int>cnt(10 , 0);
for(auto c : s) cnt[c - '0'] ++;
int res = 0, dx = 0 , ct = 0;
for(int i = 0 ; i < 10 ; ++i){
if(cnt[i] == 0) continue;
while(cnt[i]){
if(ct < 2) res += i * 10;
else res += i;
--cnt[i];
++ct;
}
}
return res;
}
};
5985. 根據給定數字劃分數組
題目描述：給你一個長度為\(n\)的數組\(nums\)，和一個分界數\(x\)，讓你将數組中小于\(x\)的數字放在所有\(x\)的左邊且不改變其原來的相對順序，将數組中大于\(x\)的數字放在所有\(x\)的右邊且不改變其原來的相對順序。
思路：根據題意模拟即可。
時間複雜度：\(O(n)\)
class Solution {
public:
vector<int> pivotArray(vector<int>& nums, int pivot) {
vector<int>res , rs;
int cnt = 0;
for(auto num : nums){
if(num < pivot) res.push_back(num);
else if(num == pivot) ++cnt;
else rs.push_back(num);
}
for(int i = 1 ; i <= cnt ; ++i) res.push_back(pivot);
for(auto num : rs) res.push_back(num);
return res;
}
};
5986. 設定時間的最少代價
題目描述：自己看題目吧
思路：根據題意，将時間先表示成\(m : s\)的形式其中\(s < 60\)，注意可能會存在\(m > 99\)的情況，需要特判。然後表示成\(4\)位，去除前導\(0\)之後計算價值。然後再\(m \neq 0 , s \leq 39\)的情況下表示\(m - 1 : s + 60\)。在算一次價值。二者取最小即可。
class Solution {
public:
int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
auto solve = [&](vector<int>& target){
reverse(target.begin() , target.end());
while(target.back() == 0) target.pop_back();
reverse(target.begin() , target.end());
int cur = startAt, res = 0;
for(auto num : target){
if(num == cur) res += pushCost;
else res += pushCost + moveCost;
cur = num;
}
return res;
};
int m = targetSeconds / 60 , s = targetSeconds % 60;
if(m > 99) --m , s += 60;
vector<int>nums(4 , 0);
auto process = [&](vector<int>& nums , int m ,int s){
nums[0] = m / 10;nums[1] = m % 10;
nums[2] = s / 10; nums[3] = s % 10;
return ;
};
process(nums , m , s);
int res = solve(nums);
nums = vector<int>(4 , 0);
if(m && s <= 39){
--m;s += 60;
process(nums , m , s);
res = min(res , solve(nums));
}
return res;
}
};
5987. 删除元素後和的最小內插補點
題目描述：給你一個長度為\(3 * n\)的數組\(nums\)，讓你删除其中的\(n\)個，對于删除後的數組，定義其前\(n\)個數字的和為\(sum_{first}\)，後\(n\)個數字的和為\(sum_{second}\)。求\(sum_{first} - sum_{second}\)的最小值。
思路：顯然我們要最小化\(sum_{first}\)，最大化\(sum_{second}\)。考慮定義分界點\(n - 1 \leq p < 2 *n\)。區間
[0 , p]
包含第一部分的所有元素，根據貪心政策需要删除其中\(p - n + 1\)個最大的元素，而區間
[p + 1 , 3 * n - 1]
包含第二部分的所有元素，根據貪心政策，需要删除其中$2 * n - p - 1 $個最小的元素。考慮如何維護，對于第一部分，使用一個大根堆即可；對于第二部分，我們使用兩個
multiset
a , b
分别存儲較小的\(2 * n - p - 1\)個元素和較大的\(n\)個元素，若移動分界點對應的元素在
a
中存在，則直接删除，否則在
b
中删除該元素，并将
a
中的最大值加入
b
中。
時間複雜度：\(O(nlogn)\)
class Solution {
public:
long long minimumDifference(vector<int>& nums) {
priority_queue<int>heap;
long long sum = 0;
int n = nums.size();
int m = n / 3;
for (int i = 0; i < m; ++i) {
sum += nums[i];
heap.push(nums[i]);
}
multiset<int> a, b;
for (int i = m; i < n; ++i) {
if (b.size() < m) {
sum -= nums[i];
b.insert(nums[i]);
}
else {
if (*b.begin() >= nums[i]) a.insert(nums[i]);
else {
int dx = *b.begin();
a.insert(*b.begin());
b.erase(b.begin());
b.insert(nums[i]);
sum += dx - nums[i];
}
}
}
long long res = sum;
for (int i = m; i < 2 * m; ++i) {
if (a.find(nums[i]) != a.end()) {
a.erase(a.find(nums[i]));
}
else {
b.erase(b.find(nums[i]));
int dx = *a.rbegin();
sum += nums[i] - dx;
b.insert(dx);
a.erase(a.find(dx));
}
if (nums[i] < heap.top()) {
sum -= heap.top();
heap.pop();
heap.push(nums[i]);
sum += nums[i];
}
res = min(res, sum);
}
return res;
}
};