贪心4

贪心4

1675. 数组的最小偏移量

#include <iostream>
#include <vector>
#include <set>

using namespace std;

class Solution {
public:
    // 返回数组执行某些操作后可以拥有的最小偏移量
    int minimumDeviation(vector<int> &nums) {
        // 使用 multiset 维护有序集合
        multiset<int> s;

        // 初始化：将所有元素变为偶数插入 multiset 中
        for (int num: nums) {
            if (num % 2 == 0) {
                s.insert(num);         // 偶数直接插入
            } else {
                s.insert(num * 2);     // 奇数先乘2变为偶数再插入
            }
        }

        int res = *s.rbegin() - *s.begin();  // 当前最大偏移量

        // 尽可能减小最大值（最大值为偶数时可以继续除2）
        while (res > 0 && *s.rbegin() % 2 == 0) {
            int maxVal = *s.rbegin();        // 当前最大值
            s.erase(prev(s.end()));          // 删除最大值
            s.insert(maxVal / 2);            // 插入最大值的一半
            res = min(res, *s.rbegin() - *s.begin());  // 更新最小偏移量
        }

        return res;
    }
};

781. 森林中的兔子

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 根据兔子的回答，计算森林中最少有多少只兔子
    int numRabbits(vector<int> &arr) {
        // 先排序，让相同回答的兔子聚集在一起
        sort(arr.begin(), arr.end());
        int n = arr.size();
        int res = 0;

        // 遍历排序后的数组
        for (int i = 0, j = 1, x; i < n; j++) {
            x = arr[i];
            // 扩展到所有连续相同回答的兔子
            while (j < n && arr[j] == x) j++;
            // i 到 j - 1 是回答为 x 的兔子，共有 j - i 个
            // 每组最多可以有 x + 1 只兔子（包括自己和回答中提到的）
            // 把这连续的 j - i 个进行分组，每组的兔子数为 x + 1，凑不成一组的也按照一组算，即 (j - i) / (x + 1) 向上取整
            // a / b 向上取整：(a + b - 1) / b
            // (j - i) / (x + 1) 向上取整：(j - i + x + 1 - 1) / (x + 1) = (j - i + x) / (x + 1)
            // 需要 (j - i + x) / (x + 1) 组，每组 x + 1 只
            res += ((j - i + x) / (x + 1)) * (x + 1);
            i = j;  // 进入下一组的起始位置
        }

        return res;
    }
};

2449. 使数组相似的最少操作次数

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 将数组 nums 变得与 target 相似的最少操作次数
    // nums[i] + 2, nums[j] - 2 操作可以进行任意次，要求最终元素频率相同
    long long makeSimilar(vector<int> &nums, vector<int> &target) {
        int n = nums.size();
        int oddSize = split(nums);
        split(target);

        // 奇偶分别排序
        sort(nums.begin(), nums.begin() + oddSize);       // 奇数部分
        sort(nums.begin() + oddSize, nums.end());         // 偶数部分
        sort(target.begin(), target.begin() + oddSize);
        sort(target.begin() + oddSize, target.end());

        long long res = 0;
        for (int i = 0; i < n; i++)
            res += abs((long long) nums[i] - target[i]);

        // 每次操作会让差值减少4（+2 -2），所以结果除以4
        return res / 4;
    }

    // 将数组分为奇数和偶数部分（奇数排在前面），返回奇数部分长度
    int split(vector<int> &arr) {
        int oddSize = 0;
        for (int i = 0; i < arr.size(); i++)
            if (arr[i] % 2 == 1)
                swap(arr[i], arr[oddSize++]);
        return oddSize;
    }
};

知识竞赛

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAXN = 200001;
int n;
pair<int, int> nums[MAXN];

// 计算最大 min((ai+aj)/2, (bi+bj)/2) * 2 的值
int compute() {
    // 根据 abs(ai - bi) 从小到大排序
    sort(nums, nums + n, [](const pair<int, int> &a, const pair<int, int> &b) {
        return abs(a.first - a.second) < abs(b.first - b.second);
    });

    int maxA = nums[0].first;
    int maxB = nums[0].second;
    int res = 0;

    for (int i = 1; i < n; ++i) {
        if (nums[i].first <= nums[i].second) {
            res = max(res, maxA + nums[i].first);
        } else {
            res = max(res, maxB + nums[i].second);
        }
        maxA = max(maxA, nums[i].first);
        maxB = max(maxB, nums[i].second);
    }
    return res;
}

int main() {
    while (cin >> n) {
        for (int i = 0; i < n; ++i) {
            cin >> nums[i].first >> nums[i].second;
        }
        int res = compute();
        cout << fixed;
        cout.precision(1);
        cout << (double) res / 2 << '\n';
    }
    return 0;
}

将数组分成几个递增序列

#include <iostream>
#include <vector>
#include <algorithm>

// 将数组分成几个递增序列
// 给你一个有序的正数数组 nums 和整数 K
// 判断该数组是否可以被分成一个或几个长度至少为 K 的不相交的递增子序列
// 数组中的所有数字，都要被若干不相交的递增子序列包含

using namespace std;

// 判断有序数组能否分成若干长度至少为k的递增子序列
bool canDivideIntoSubsequences(vector<int> &nums, int k) {
    int n = nums.size();
    int cnt = 1;
    // 最大词频
    int maxCnt = 1;

    for (int i = 1; i < n; ++i) {
        if (nums[i] != nums[i - 1]) {
            maxCnt = max(maxCnt, cnt);
            cnt = 1;
        } else {
            cnt++;
        }
    }
    maxCnt = max(maxCnt, cnt);

    return n / maxCnt >= k;
}

/*
 * 分成 maxCnt 个数组 vector<vector<int>> arr(maxCnt)，先把最大词频的单词一组分一个
 * 然后最大词频左边的所有数字，按照 arr 下标大小 0，1，2...maxCnt-1，0，1... 一组一个
 * 最大词频右边的所有数字，按照下标逆序一组一个，maxCnt-1，maxCnt-2...2，1，0，maxCnt-1...
 * 使得所有数字尽量平均给每个数组
 */
int main() {
    // 示例：nums = [1,2,2,3,3,3], k = 2
    vector<int> nums = {1, 2, 2, 3, 3, 3};
    int k = 2;

    if (canDivideIntoSubsequences(nums, k)) {
        cout << "true\n";
    } else {
        cout << "false\n";
    }

    return 0;
}

871. 最低加油次数

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

class Solution {
public:
    // 计算从起点出发到达目标位置所需的最少加油次数
    int minRefuelStops(int target, int startFuel, vector<vector<int>> &stations) {
        // 如果起始油量已经足够到达终点，直接返回 0
        if (startFuel >= target) return 0;

        // 大根堆：用于保存沿途经过的加油站的油量
        priority_queue<int> maxHeap;

        int to = startFuel; // 当前最远能达到的位置（初始油量）
        int cnt = 0;         // 加油次数

        // 遍历每个加油站
        for (auto &station: stations) {
            int position = station[0]; // 加油站位置
            int fuel = station[1];     // 加油站油量

            // 如果当前油量无法到达下一个加油站，就从之前路过的加油站加油
            while (!maxHeap.empty() && to < position) {
                to += maxHeap.top(); // 选择之前油量最多的加油站加油
                maxHeap.pop();
                cnt++; // 加油次数 +1
                // 如果已经够到终点，提前返回
                if (to >= target) return cnt;
            }

            // 如果加完油还是到不了这个加油站，说明无法继续
            if (to < position) return -1;

            // 当前加油站可以作为未来的备选项，存入堆中
            maxHeap.push(fuel);
        }

        // 所有加油站都过了，还没到终点，继续加油看能不能冲到终点
        while (!maxHeap.empty()) {
            to += maxHeap.top();
            maxHeap.pop();
            cnt++;
            if (to >= target) return cnt;
        }

        // 到这里说明油量耗尽也到不了终点
        return -1;
    }
};