贪心6

贪心6

1921. 消灭怪物的最大数量

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

using namespace std;

class Solution {
public:
    int eliminateMaximum(vector<int> &dist, vector<int> &speed) {
        int n = dist.size();
        // 每个怪物到达城市所需的时间（向上取整）
        vector<int> time(n);
        for (int i = 0; i < n; ++i) {
            // a / b 向上取整： (a + b - 1) / b
            time[i] = (dist[i] + speed[i] - 1) / speed[i];
        }
        // 按照到达时间从早到晚排序
        sort(time.begin(), time.end());
        for (int i = 0; i < n; ++i) {
            // 第 i 分钟只能消灭第 i 个到达的怪物
            // 有怪物提前或同时到达，游戏失败
            if (time[i] <= i) return i;
        }
        return n; // 成功消灭所有怪物
    }
};

2384. 最大回文数字

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

using namespace std;

class Solution {
public:
    string largestPalindromic(string num) {
        int n = num.size();
        // 用 ASCII 值建表，cnts['0'] ~ cnts['9'] 表示各个数字出现次数
        vector<int> cnts(58, 0);
        // 统计每个字符的出现次数
        for (char c: num) cnts[c]++;

        string left;  // 回文左半部分
        char mid = 0; // 回文中心字符（出现奇数次的最大数字）

        // 先从 '9' 到 '1'，为回文构造左半部分（跳过 '0' 是为了避免前导零）
        for (char i = '9'; i >= '1'; --i) {
            // 如果当前字符出现奇数次，并且还没有选中中心字符，就选它
            if ((cnts[i] & 1) && mid == 0) mid = i;
            // 将一半数量的字符放到左半部分
            left += string(cnts[i] / 2, i);
        }

        // 如果左半部分是空的（说明所有数字都只出现 0 次或 1 次）
        if (left.empty()) {
            if (mid == 0) {
                return "0"; // 没有任何可构造的数字，只能返回 "0"
            } else {
                return string(1, mid); // 返回唯一的中心字符
            }
        }

        // 将 '0' 补到左半部分，注意：'0' 不会出现在最前面，因为前面已构造过有效数字
        left += string(cnts['0'] / 2, '0');

        // 构造右半部分为左半部分的反转
        string right = left;
        reverse(right.begin(), right.end());

        // 如果还没有选中中心字符，但 '0' 出现了奇数次，那就用 '0' 做中心
        if (mid == 0 && (cnts['0'] & 1))
            mid = '0';

        // 返回结果：左半 + 中心 + 右半
        if (mid != 0) return left + mid + right;
        return left + right;
    }
};

1792. 最大平均通过率

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

using namespace std;

class Solution {
public:
    struct ClassInfo {
        int pass;
        int total;

        // 比较器：通过率提升大的优先
        bool operator<(const ClassInfo& other) const {
            double currGain = (double)(pass + 1) / (total + 1) - (double)pass / total;
            double otherGain = (double)(other.pass + 1) / (other.total + 1) - (double)other.pass / other.total;
            return currGain < otherGain;
        }
    };

    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        priority_queue<ClassInfo> pq;

        // 初始化堆
        for (auto& c : classes) {
            pq.push({c[0], c[1]});
        }

        // 分配聪明学生
        while (extraStudents--) {
            ClassInfo top = pq.top();
            pq.pop();
            pq.push({top.pass + 1, top.total + 1});
        }

        // 累加平均通过率
        double totalRatio = 0.0;
        while (!pq.empty()) {
            ClassInfo cls = pq.top();
            pq.pop();
            totalRatio += (double)cls.pass / cls.total;
        }

        return totalRatio / classes.size();
    }
};

857. 雇佣 K 名工人的最低成本

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

using namespace std;

struct Employee {
    double ratio; // 薪水与质量的比例 wage[i] / quality[i]
    int quality;  // 工作质量

    Employee(double r, int q) : ratio(r), quality(q) {}
};

class Solution {
public:
    // 计算雇佣 k 名工人的最低成本
    double mincostToHireWorkers(vector<int> &quality, vector<int> &wage, int k) {
        int n = quality.size(); // 工人数目
        vector<Employee> employees;
        employees.reserve(n);  // 预留空间，提升效率

        // 构造员工数组，计算每个员工的薪资质量比
        for (int i = 0; i < n; ++i) {
            employees.emplace_back((double) wage[i] / quality[i], quality[i]);
        }

        // 按比例从小到大排序
        sort(employees.begin(), employees.end(), [](const Employee &a, const Employee &b) {
            return a.ratio < b.ratio;
        });

        // 创建一个大根堆（priority_queue默认是大根堆）
        // 用来维护当前选中员工的质量，方便弹出最大质量员工以控制质量和最小化
        priority_queue<int> maxHeap;

        // 当前堆中所有员工的质量和
        int qualitySum = 0;
        // 记录最低成本，初始设为无穷大
        double res = numeric_limits<double>::max();

        // 遍历排序后的员工数组，尝试以当前员工的比例作为组内最大比例
        for (int i = 0; i < n; ++i) {
            maxHeap.push(employees[i].quality);
            qualitySum += employees[i].quality;

            // 如果当前选中员工数量超过 k，移除质量最大的那个以保证只雇佣 k 人
            if ((int) maxHeap.size() > k) {
                qualitySum -= maxHeap.top();
                maxHeap.pop();
            }

            // 当选中 k 个员工时，计算当前方案的成本
            if ((int) maxHeap.size() == k) {
                // 成本 = 质量和 * 当前员工的薪资质量比
                // 由于排序，当前员工的 ratio 是所选组内最大薪资质量比，保证满足所有员工的最低工资要求
                res = min(res, qualitySum * employees[i].ratio);
            }
        }

        return res;
    }
};

使用：

vector<Employee> employees;
employees.reserve(n);
for (int i = 0; i < n; ++i) {
    employees.emplace_back((double)wage[i] / quality[i], quality[i]);
}

vector size 初始为 0，capacity 为 n，每次 emplace_back() 真正创建一个对象并放到末尾，没有无用对象生成，性能优，语义明确。

而不是：

vector<Employee> employees(n);
for (int i = 0; i < n; ++i) {
    employees[i] = Employee((double)wage[i] / quality[i], quality[i]);
}

vector size 初始为 n，capacity 也是 n，会立即调用 Employee 的默认构造函数 n 次来初始化这 n 个对象（即使很快会覆盖它们），接着再用赋值运算符 = 去替换这些对象的值（调用拷贝赋值运算符）。

所以：

• 多了一次默认构造 + 一次赋值
• 若 Employee 构造开销大（比如有复杂成员），就会 影响性能
• 而且必须保证 Employee 提供了 **默认构造函数，否则会编译错误

3211 砍树

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

using namespace std;

// 每棵树的信息
struct Tree {
    int initWeight;  // 初始重量
    int growWeight;  // 每天增重
};

// 功能函数：计算最大收益
int computeMaxProfit(const vector<Tree> &trees, int m) {
    int n = trees.size();
    // 排序：增长慢的树尽早砍，增长快的树尽可能晚砍
    vector<Tree> sortedTrees = trees;
    sort(sortedTrees.begin(), sortedTrees.end(), [](const Tree &a, const Tree &b) {
        return a.growWeight < b.growWeight;
    });

    // dp[i][j]：前 i 棵树，选 j 棵砍，最大收益
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // 两种选择：不选第 i 棵树，或在第 j 天砍第 i 棵树
            dp[i][j] = max(
                    dp[i - 1][j],
                    dp[i - 1][j - 1] + sortedTrees[i - 1].initWeight + sortedTrees[i - 1].growWeight * (j - 1)
            );
        }
    }
    return dp[n][m];
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;

        vector<int> init(n), grow(n);
        for (int i = 0; i < n; ++i) cin >> init[i];
        for (int i = 0; i < n; ++i) cin >> grow[i];

        vector<Tree> trees(n);
        for (int i = 0; i < n; ++i)
            trees[i] = Tree{init[i], grow[i]};

        int res = computeMaxProfit(trees, m);
        cout << res << '\n';
    }

    return 0;
}