贪心2

贪心2

LCR 132. 砍竹子 II

#include <iostream>

using namespace std;

class Solution {
public:
    const int MOD = 1e9 + 7;

    // 快速幂算法，计算 (x^n) % mod
    long long power(long long x, int n, int mod) {
        long long res = 1;
        // 快速幂核心：将 n 看作二进制，从低位到高位逐位处理
        while (n > 0) {
            // 当前位是 1，则将当前的 x 乘进结果
            if (n & 1) res = (res * x) % mod;
            // x 每轮变成 x^2
            x = (x * x) % mod;
            // 处理下一位
            n >>= 1;
        }
        return res;
    }

    // 主函数：返回将长度为 n 的竹子剪成若干段后，长度乘积的最大值
    int cuttingBamboo(int n) {
        // 特殊情况处理：长度为 2 或 3 的竹子不能再剪，直接返回最大乘积
        if (n == 2) return 1;
        if (n == 3) return 2;

        // 贪心策略：尽可能多剪 3，因为乘积最大
        // 如果 n % 3 == 0，完全由 3 构成，尾数为 1
        // 如果 n % 3 == 1，多余一个 1，要拆成 3 + 1 -> 2 + 2，尾数为 4
        // 如果 n % 3 == 2，直接留下 2，尾数为 2
        int tail = (n % 3 == 0) ? 1 : ((n % 3 == 1) ? 4 : 2);

        // pow3 表示剪下多少个 3 的段数
        int pow3 = (tail == 1 ? n : (n - tail)) / 3;

        // 最终结果为 (3 的 pow3 次方 * tail) % MOD
        return (int) (power(3, pow3, MOD) * tail % MOD);
    }
};

分成 k 份的最大乘积

#include <iostream>
#include <vector>
#include <climits>
#include <cstdlib>

using namespace std;

class Solution {
public:
    // 模数，用于防止乘积溢出
    const int MOD = 1e9 + 7;

    // ===============================
    // 方法1：暴力递归（仅适用于小范围验证）
    // ===============================
    // 入口函数
    int maxValue1(int n, int k) {
        return f1(n, k);
    }

    // 将 rest 分成 k 份，返回最大乘积（纯暴力尝试所有可能的切法）
    int f1(int rest, int k) {
        // 如果只需要切成一份，直接返回剩下的值
        if (k == 1) return rest;
        int res = INT_MIN;
        // 当前尝试第一刀切出 cur，剩下 rest - cur 交给下一层递归去切成 k - 1 份
        for (int cur = 1; cur <= rest && (rest - cur) >= (k - 1); cur++) {
            int curRes = cur * f1(rest - cur, k - 1);
            res = max(res, curRes);
        }
        return res;
    }

    // ===============================
    // 方法2：贪心解法（用于处理 n, k 非常大时的情况）
    // ===============================
    // 将 n 分成 k 份，每一份尽量均分（相差不超过 1），使乘积最大
    int maxValue2(long long n, long long k) {
        long long a = n / k;       // 平均每段为 a
        long long b = n % k;       // 有 b 段需要加 1（也就是 a + 1）
        // 有 b 段长度是 a + 1，k - b 段是 a
        long long part1 = power(a + 1, b, MOD);        // (a + 1)^b
        long long part2 = power(a, k - b, MOD);        // a^(k - b)
        return (int) (part1 * part2 % MOD);             // 两部分乘起来再取模
    }

    // 快速幂计算：返回 (x^n) % mod
    long long power(long long x, long long n, int mod) {
        long long res = 1;
        // 快速幂模板：将 n 的每一位从低到高处理
        while (n > 0) {
            if (n & 1) res = (res * x) % mod;
            x = (x * x) % mod;
            n >>= 1;
        }
        return res;
    }

    // ===============================
    // 对数器：用于验证贪心方法的正确性
    // ===============================
    void test() {
        int N = 30;              // 最大测试的 n
        int testTimes = 2000;    // 测试次数
        cout << "测试开始" << endl;
        for (int i = 1; i <= testTimes; i++) {
            int n = rand() % N + 1;         // 随机 n：1~N
            int k = rand() % n + 1;         // 随机 k：1~n
            int ans1 = maxValue1(n, k);     // 暴力解
            int ans2 = maxValue2(n, k);     // 贪心解
            if (ans1 != ans2) {
                // 出错就打印详细信息
                cout << "出错了！n = " << n << ", k = " << k << endl;
                cout << "暴力解 = " << ans1 << ", 贪心解 = " << ans2 << endl;
                break;
            }
            if (i % 100 == 0) {
                cout << "测试到第 " << i << " 组" << endl;
            }
        }
        cout << "测试结束" << endl;
    }
};

int main() {
    Solution sol;
    sol.test();
    return 0;
}

435. 无重叠区间

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <climits>

using namespace std;

class Solution {
public:
    // 正式解法：贪心策略，时间复杂度 O(nlogn)
    // 每次选择结束时间最早的会议加入，保证能安排更多会议
    int maxMeeting2(vector<vector<int>>& meeting) {
        sort(meeting.begin(), meeting.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1]; // 按照结束时间升序排序
        });

        int n = meeting.size();
        int res = 0;
        int cur = -1; // 当前时间线，初始化为 -1

        for (int i = 0; i < n; ++i) {
            if (cur <= meeting[i][0]) { // 当前会议不冲突，可以安排
                res++;
                cur = meeting[i][1]; // 更新时间线为当前会议的结束时间
            }
        }
        return res;
    }

    // 变形题解法：LeetCode 原题求最少删除多少会议 -> 总会议数 - 最多能安排的会议数
    int eraseOverlapIntervals(vector<vector<int>>& meeting) {
        int keep = maxMeeting2(meeting);
        return meeting.size() - keep;
    }

    // 暴力解法：尝试所有排列，时间复杂度 O(n!)
    // 仅用于小样本验证
    int maxMeeting1(vector<vector<int>>& meeting) {
        return f(meeting, meeting.size(), 0);
    }

    // 递归尝试全排列，从第 i 个位置开始排列
    int f(vector<vector<int>>& meeting, int n, int i) {
        int res = 0;
        if (i == n) {
            int count = 0, cur = -1;
            for (int j = 0; j < n; ++j) {
                if (cur <= meeting[j][0]) {
                    count++;
                    cur = meeting[j][1];
                }
            }
            res = count;
        } else {
            for (int j = i; j < n; ++j) {
                swap(meeting[i], meeting[j]);
                res = max(res, f(meeting, n, i + 1));
                swap(meeting[i], meeting[j]);
            }
        }
        return res;
    }

    // 随机生成会议数组：每个会议是一个 [start, end)
    vector<vector<int>> randomMeeting(int n, int m) {
        vector<vector<int>> ans(n, vector<int>(2));
        for (int i = 0; i < n; ++i) {
            int a = rand() % m;
            int b = rand() % m;
            if (a == b) {
                ans[i][0] = a;
                ans[i][1] = a + 1;
            } else {
                ans[i][0] = min(a, b);
                ans[i][1] = max(a, b);
            }
        }
        return ans;
    }

    // 对数器测试：验证暴力解和贪心解是否一致
    void test() {
        int N = 10; // 最大会议数（用于暴力验证）
        int M = 12; // 最大时间范围
        int testTimes = 2000;
        cout << "测试开始" << endl;
        for (int i = 1; i <= testTimes; ++i) {
            int n = rand() % N + 1;
            vector<vector<int>> meeting = randomMeeting(n, M);
            vector<vector<int>> copy = meeting; // 防止 maxMeeting1 排列破坏原数据
            int ans1 = maxMeeting1(meeting);
            int ans2 = maxMeeting2(copy);
            if (ans1 != ans2) {
                cout << "出错了！n = " << n << endl;
                cout << "暴力 = " << ans1 << ", 贪心 = " << ans2 << endl;
                break;
            }
            if (i % 100 == 0) {
                cout << "测试到第 " << i << " 组" << endl;
            }
        }
        cout << "测试结束" << endl;
    }
};

int main() {
    Solution sol;
    sol.test();
    return 0;
}

P1803 凌乱的yyy / 线段覆盖

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

using namespace std;

const int MAXN = 1000001;

// latest[end] 表示所有以end结束的会议中，最晚的开始时间
// 如果没有会议以 end 结束，则为 -1
vector<int> latest(MAXN, -1);

int n;

// 计算最多可安排的会议数量（不排序，利用时间线遍历）
int compute() {
    int res = 0;
    int cur = 0; // 当前时间线，之前的时间都不能安排新的会议了
    // 遍历所有可能的结束时间
    for (int end = 0; end < MAXN; ++end) {
        // 如果存在以 end 结束的会议，且当前时间 cur <= 该会议的最晚开始时间
        // 说明可以安排这场会议
        if (cur <= latest[end]) {
            res++;
            cur = end; // 安排会议后，更新当前时间线为会议结束时间
        }
    }
    return res;
}

int main() {
    while (cin >> n) {
        // 初始化latest数组，-1表示没有会议以该时间结束
        fill(latest.begin(), latest.end(), -1);

        for (int i = 0; i < n; ++i) {
            int start, end;
            cin >> start >> end;
            // 如果第一次遇到以end结束的会议，直接赋值
            if (latest[end] == -1) {
                latest[end] = start;
            } else {
                // 更新最晚开始时间
                latest[end] = max(latest[end], start);
            }
        }

        cout << compute() << "\n";
    }

    return 0;
}

1353. 最多可以参加的会议数目

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

using namespace std;

class Solution {
public:
    // 会议只占一天的最大会议数量
    // 给定若干会议的开始、结束时间
    // 任何会议召开期间，只需抽一天参加，且该天只能参加一个会议
    // 返回能参加的最大会议数量
    int maxEvents(vector<vector<int>> &events) {
        int n = events.size();
        if (n == 0) return 0;

        // 按开始时间升序排序
        sort(events.begin(), events.end(), [](const vector<int> &a, const vector<int> &b) {
            return a[0] < b[0];
        });

        // 找到最早的开始时间和最晚的结束时间
        int minDay = events[0][0];
        int maxDay = events[0][1];
        for (int i = 1; i < n; ++i)
            maxDay = max(maxDay, events[i][1]);

        // 小根堆，存储当前可参加的会议的结束时间
        priority_queue<int, vector<int>, greater<int>> minHeap;

        int res = 0; // 参加会议的数量
        int i = 0;   // 事件索引

        // 从最早开始时间到最晚结束时间按天遍历
        for (int day = minDay; day <= maxDay; ++day) {
            // 将所有在当前天开始的会议加入堆
            while (i < n && events[i][0] == day) {
                minHeap.push(events[i][1]);
                i++;
            }

            // 清除已结束的会议（结束时间小于当前天）
            while (!minHeap.empty() && minHeap.top() < day)
                minHeap.pop();

            // 如果有可参加的会议，参加结束时间最早的那个
            if (!minHeap.empty()) {
                minHeap.pop();
                res++;
            }
        }

        return res;
    }
};

502. IPO

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

class Solution {
public:
    struct Project {
        int profit;
        int capital;

        Project(int p, int c) : profit(p), capital(c) {}
    };

    int findMaximizedCapital(int k, int w, vector<int> &profits, vector<int> &capital) {
        int n = profits.size();
        auto cmpCapital = [](const Project &a, const Project &b) {
            return a.capital > b.capital; // 小根堆
        };
        auto cmpProfit = [](const Project &a, const Project &b) {
            return a.profit < b.profit; // 大根堆
        };

        // 启动资金的小根堆
        priority_queue<Project, vector<Project>, decltype(cmpCapital)> minCapitalHeap(cmpCapital);
        // 利润的大根堆
        priority_queue<Project, vector<Project>, decltype(cmpProfit)> maxProfitHeap(cmpProfit);

        for (int i = 0; i < n; i++)
            minCapitalHeap.emplace(profits[i], capital[i]);

        while (k > 0) {
            // 把所有启动资金 <=w 的项目转移到大根堆
            while (!minCapitalHeap.empty() && minCapitalHeap.top().capital <= w) {
                maxProfitHeap.push(minCapitalHeap.top());
                minCapitalHeap.pop();
            }
            // 没有可做项目了
            if (maxProfitHeap.empty()) break;
            // 做利润最高的项目
            w += maxProfitHeap.top().profit;
            maxProfitHeap.pop();
            k--;
        }
        return w;
    }
};

加入差值绝对值直到长度固定

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <unordered_set>
#include <unordered_map>

using namespace std;


// 加入差值绝对值直到长度固定
// 给定一个非负数组 arr，计算任何两个数差值的绝对值
// 如果 arr 中没有，都要加入到 arr 里，但是只加一份
// 然后新的 arr 继续计算任何两个数差值的绝对值，
// 如果 arr 中没有，都要加入到 arr 里，但是只加一份
// 一直到 arr 大小固定，返回 arr 最终的长度


// 检查当前集合是否已经稳定
// 遍历 list 中的所有数对，计算它们的差值，若差值不在集合中，则加入
// 若本轮操作前后 list 长度不变，说明已经没有新数可以加了，返回 true；否则返回 false
bool finish(vector<int> &list, unordered_set<int> &st) {
    int len = list.size();
    for (int i = 0; i < len; ++i) {
        for (int j = i + 1; j < len; ++j) {
            int val = abs(list[i] - list[j]);
            if (st.find(val) == st.end()) {
                list.emplace_back(val);  // 添加新差值
                st.emplace(val);         // 标记已存在
            }
        }
    }
    return len == list.size(); // 如果没有新增元素，说明完成
}

// 暴力方法：不断尝试加差值，直到集合不再扩展
int len1(vector<int> &arr) {
    vector<int> list(arr);                         // 拷贝数组
    unordered_set<int> st(begin(arr), end(arr));   // 初始化哈希集合
    while (!finish(list, st));                     // 不断尝试加入新差值
    return list.size();                            // 返回最终集合大小
}

// 计算最大公约数
int gcd(int m, int n) {
    return n == 0 ? m : gcd(n, m % n);
}

// 优化方法：基于最大公约数和最大值数学推导
int len2(vector<int> &arr) {
    int maxVal = 0;  // 最大值
    int g = 0;       // 所有非 0 元素的 GCD（最大公约数）

    // 初始化 maxVal 和 g
    for (const auto &num: arr) {
        maxVal = max(maxVal, num);
        if (num != 0) g = num;
    }

    // 如果数组全是 0，直接返回原数组长度
    if (g == 0) return arr.size();

    unordered_map<int, int> cnts; // 统计每个数出现次数
    for (const auto &num: arr) {
        if (num != 0) g = gcd(g, num); // 更新整体 GCD
        cnts[num]++;
    }

    // 计算最终结果，先计算至少的长度 max / g
    // 比如最大值为 100，最小公约数是 5，那么5、10、15、20...100 都会在最终的数组里，共 max / g 个
    int res = maxVal / g;
    int maxCnt = 0;

    // 对于非 0 的重复数字，每多一个都要额外 +1
    for (const auto &item: cnts) {
        // 已经在 res 中算过一个了，所以 -1
        if (item.first != 0) res += item.second - 1;
        maxCnt = max(maxCnt, item.second); // 记录最大重复次数
    }

    if (cnts.find(0) != cnts.end()) {
        // 原始数组中原本就有 0，加上次数
        res += cnts[0];
    } else {
        // 最大重复次数大于一，说明有相同的数字，说明数组需要增加一个 0
        res += maxCnt > 1 ? 1 : 0;
    }

    return res;
}

// 生成长度为 n、元素值范围为 [0, v) 的随机数组
vector<int> randomArray(int n, int v) {
    vector<int> ans(n);
    for (int i = 0; i < n; ++i)
        ans[i] = rand() % v;
    return ans;
}

int main() {
    srand(time(nullptr));  // 初始化随机种子
    const int N = 50;      // 数组最大长度
    const int V = 100;     // 元素最大值
    const int testTimes = 20000; // 测试次数

    cout << "测试开始" << endl;
    for (int i = 0; i < testTimes; ++i) {
        int n = rand() % N + 1;              // 随机长度
        vector<int> nums = randomArray(n, V); // 随机数组
        int ans1 = len1(nums);                // 暴力方法
        int ans2 = len2(nums);                // 数学方法

        if (ans1 != ans2) {
            cout << "出错了！" << endl;
            for (int x: nums) cout << x << " ";
            cout << endl << "len1=" << ans1 << ", len2=" << ans2 << endl;
            break; // 出错立即终止
        }
    }
    cout << "测试结束" << endl;
    return 0;
}