当前位置：首页 > article >正文

贪心算法

article 2025/2/24 1:20:25

int a[1000], b=5, c=8;
swap(b, c); // 交换操作
memset(a, 0, sizeof(a)); // 初始化为0或-1

引导问题

为一个小老鼠准备了M磅的猫粮，准备去和看守仓库的猫做交易，因为仓库里有小老鼠喜欢吃的五香豆，第i个房间有J[i] 磅的五香豆，并且需要用F[i]磅的猫粮去交换；求老鼠最多可换多少豆？若五香豆不能全换猫粮，按比例换。

Sample Input
5 3 ——M猫粮 N房间
7 2 ——五香豆猫粮
4 3
5 2
-1 -1 —— 结束

Sample Output
13.333

由按比例换，7/2=3.5 4/3=1.333... 5/2=2.5 3.5最大排序，一次换——7+5+1.3333=13.333

初识贪心

在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体上加以考虑，所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。

例题

1.田忌赛马

每个马跟比自己弱的程度最小的马

1.排序

2.蓝色最大和红色最大比较，看蓝色能不能比过红色，若比不过，拿蓝色最小的跟红色比

3.拿蓝色最大跟红色第二大的比...能比就比，不能就继续拿最差的跟最好的比

反证法上大分~事件序列问题

已知N个事件的发生时刻和结束时刻。

一些在时间上没有重叠的事件，可以构成一个事件序列，如事件{2，8，10}。

事件序列包含的事件数目，称为该事件序列的长度。

请编程找出一个最长的事件序列。

至少存在一个最长事件序列包含最早结束事件（最早结束事件是0）

反证法证明上句：

假设所有最长事件序列都不包含最早结束事件；只要证明这个假设是错的，原命题得证；

任取一个所谓的最长事件序列，把第一个事件去掉，换掉事件0，肯定跟后面都不冲突（因为换上的是最早结束的时间，原来都不冲突，现在更不冲突）

证明完后选中最早结束事件0 后面我做类似的：每次找一个最早结束的事件，只要和前面的不冲突的都选中；

2.搬桌子

一个公司要做调整搬桌子，房间有400个，一边是单号，一边双号；

走廊很窄，只通过1个桌子过；

输入：

第二行：趟数

第三行：房间号：10号搬到20号

每趟搬要10min：不重叠可以同时搬，要10min；重叠要分开搬

法一：与上题的思想差不多，只不过，改成了最早开始事件（找开始最早的）

法二：统计每个区间在时间轴上的重叠次数，并找出最大重叠次数的区间。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t, i, j, N, P[200];  // t是测试用例的数量，N是每个测试用例的区间数量
    int s, d, temp, k, MAX;  // s和d是区间的起点和终点，MAX用于记录最大重叠次数
    cin >> t;

    for (i = 0; i < t; i++) {
        // 初始化P数组，用于记录每个时间点的重叠次数
        for (j = 0; j < 200; j++)
            P[j] = 0;

        cin >> N;  // 读取当前测试用例的区间数量
        for (j = 0; j < N; j++) {
            cin >> s >> d;  // 读取区间的起点和终点
            s = (s - 1) / 2;  // 将起点转换为数组索引
            d = (d - 1) / 2;  // 将终点转换为数组索引

            // 如果起点大于终点，交换它们
            if (s > d) {
                temp = s;
                s = d;
                d = temp;
            }

            // 在区间[s, d]内的每个时间点增加计数
            for (k = s; k <= d; k++)
                P[k]++;
        }

        // 找到最大重叠次数
        MAX = -1;
        for (j = 0; j < 200; j++)
            if (P[j] > MAX)
                MAX = P[j];

        // 输出最大重叠次数乘以10
        cout << MAX * 10 << endl;
    }

    return 0;
}

3.删数问题

已知一个长度不超过240位的正整数n（其中不含有效字0），去掉其中任意s（s小于n的长度）个数字后，将剩下的数字按原来的左右次序组成一个新的正整数。

给定n和s，请编程输出最小的新正整数。

Sample Input
178543 4
Sample Output
13

法一：从左到右扫描逆序对，删掉左边的数，若没有逆序对，删掉最后一位数

1 7 8 5 4 3 —— 1 7 5 4 3 ——1 5 4 3 ——1 4 3 —— 1 3

1 2 3 4

4.青蛙的邻居

每个湖泊都有一个青蛙，如果两个湖泊之间有水渠相连，我们认为两个青蛙他们为邻居；

问：你可以画出这个湖泊分布图吗？

Sample Input

3

7 —— 青蛙个数

4 3 1 5 4 2 1 —— 第一个青蛙有4个邻居；第二个青蛙有3个邻居....

6

4 3 1 4 2 0

6

2 3 1 1 2 1

Sample Output

YES

NO

YES