贪心算法初析(1)

贪心算法初析(1)

/ 0评 / 2260次 / 1

——以“今年暑假不AC打扫牛棚”为例

这类线段覆盖问题求最大最小值大同小异

今年暑假不AC

题目描述

“今年暑假不AC?”

“是的。”

“那你干什么呢?”

“看世界杯呀,笨蛋!”

“@#$%^&*%...”

确实如此,世界杯来了,球迷的节日也来了,估计很多ACMer也会抛开电脑,奔向电视了。 作为球迷,一定想看尽量多的完整的比赛,当然,作为新时代的好青年,你一定还会看一些其它的节目,比如新闻联播(永远不要忘记关心国家大事)、非常6+7、超级女生,以及王小丫的《开心辞典》等等,假设你已经知道了所有你喜欢看的电视节目的转播时间表,你会合理安排吗?(目标是能看尽量多的完整节目)

输入格式

输入数据包含多个测试实例,每个测试实例的第一行只有一个整数\(n(n<=100)\),表示你喜欢看的节目的总数,然后是\(n\)行数据,每行包括两个数据\(Ti_s,Ti_e\) \((1<=i<=n)\),分别表示第\(i\)个节目的开始和结束时间,为了简化问题,每个时间都用一个正整数表示。\(n=0\)表示输入结束,不做处理。

输出格式

对于每个测试实例,输出能完整看到的电视节目的个数,每个测试实例的输出占一行

题目分析

先化解题意(这题B话属实多)

有\(n\)个线段,分别给定长度。要求最多能在其中选取多少条使得他们不首尾覆盖地排列

注意:\([1,i]与[i,j]\)相互之间不覆盖

那么这就是到贪心算法的用武之地了,贪心算法的核心是要去作出当前情况下所能作出的最“贪”的选择,而不用考虑之后的影响。说白了,就是你面前有一张10块和一张100。那肯定是拿那张100的,至于那张10块的,谁去拿,他够不够都不在我们的考虑范围之内。

就这一题而言,我现在肯定优先选择我当前情况下,所能选取的(开始时间肯定要大于等于我上个节目的结束时间),结束时间最早的节目去看。

那么,代码就顺理成章了

Accepted Code

/*
 * @Author: Gehrychiang
 * @Date: 2020-01-21 13:17:11
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#include <bits/stdc++.h>
using namespace std;
struct $
{
    int st;
    int en;
};
$ cls[1000005];
bool comp($ a, $ b)
{
    if (a.en != b.en)
    {
        return a.en < b.en;
    }
    else
    {
        return a.st < b.st;
    }
}
int main()
{
    int n;
    while (cin >> n, n != 0)
    {
        memset(cls, 0, sizeof(cls));
        for (int i = 0; i < n; i++)
        {
            cin >> cls[i].st >> cls[i].en;//读取
        }
        sort(cls, cls + n, comp);//按照结束时间优先排序,将结束的早的放在前面
        int cur_end = 0;//记录我当前的结束时间
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            if (cls[i].st >= cur_end)//这个可以选取
            {
                cur_end = cls[i].en;//更新结束时间
                ++cnt;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

打扫牛棚

题目描述

大表哥分配 N \((1 <= N <= 25000)\) 只中的一些奶牛在牛棚附近做些清洁。 他总是要让至少一只牛做清洁。他把一天分成T段\((1 <= T <= 1000000)\), 第一段是\(1\),最后一段是\(T\)

每只奶牛只在一些时间段有空。奶牛如果选择某一段时间,则必须完成整段时间的工作

你的任务是帮助他安排一些奶牛,使每段时间至少有一只奶牛被安排来做这件事。并且奶牛数应尽可能小。如果不可能办到,输出\(-1\)

输入格式

* 第一行:\(N\)和\(T\)
* 第二行至\(N+1\)行: 每一行包括奶牛能工作的开始和结束时间。闭区间。

输出格式

每组数据一行,输出完成清洁所需最少的奶牛数,如果不可能办到,输出\(-1\)

题目分析

首先把题目翻译成人话

有一段从\(1\)到\(n\)的区间,现有多条线段(左右界不同,有重合区域),求最少需几条线段才能覆盖整个大区间?

并且根据这个题目的描述。这样的两个区间如\([1, 3]\) , \([4, 7]\)也算覆盖了\([1,7]\)

既然要达到一个最短覆盖数的效果,那么贪心策略也是比较显然的,我们肯定是要优先去选择更长的线段(直观来看)。说成比较严谨的语言,就是我要选取当前能够选取的所有情况中,结束点最大的那一条线段。

这样的实现也并不复杂,我们还是和上一条一样,利用一个cur_end变量去记录当前的结束位置即可。

需要注意的几个情况主要有出现间断点的情况,这个及时break

Accepted Code

/*
 * @Author: Gehrychiang
 * @Date: 2020-02-07 13:17:49
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct $ //结构体存储每一个奶牛的开始时间和结束时间
{
    int s;
    int e;
};
$ cow[25005];
bool cmp($ a, $ b)
{
    if (a.s != b.s)
    {
        return a.s < b.s;
    }
    else
    {
        return a.e > b.e;
    }
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    int n, t;
    scanf("%d %d", &n, &t);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &cow[i].s, &cow[i].e);
    }
    //每一次都优先选择起始点比最大,结束时间最大
    sort(cow, cow + n, cmp); //优先按照开始时间排序,当开始时间相同时优先排结束时间最晚的
    int cur_end = 0;
    int cur_end_max = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (cow[i].s <= cur_end + 1) //遍历所有的能够选取的情况
        {
            cur_end_max = max(cow[i].e, cur_end_max); //选取最大值
            if (cur_end_max >= t)
            {
                ++cnt;
                break;
            }
        }
        else //已经把所有当前能够选取的情况遍历过了,需要更新情况
        {
            if (cur_end == cur_end_max) //没有得到任何变化直接break也就是说我到这个位置就已经结束位置就增加不上去了(或者说是存在了间断)
            {
                break;
            }
            cur_end = cur_end_max; //更新当前的结束位置
            cur_end_max = 0;
            ++cnt; //计数+1
            --i;   //重新从当前这个点开始遍历
        }
    }
    if (cur_end_max < t)
    {
        cout << "-1" << endl;
    }
    else
    {
        cout << cnt << endl;
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

说在最后,这两条题目一条求最大一条求最小,读者们不妨互相对照印证

发表回复

您的电子邮箱地址不会被公开。

你好 No.63969