首页 > 编程语言 > 详细

贪心算法小结

时间:2019-06-16 15:08:08      阅读:103      评论:0      收藏:0      [点我收藏+]

M-Cleaning Shifts

描述

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

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

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

输入

注意,输入包含多组测试数据,请处理到文件结束
* 第一行:N和T 
* 第二行至N+1行: 每一行包括奶牛能工作的开始和结束时间。闭区间。

输出

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

样例输入

3 10
1 7
3 6
6 10

样例输出

2

提示

这道题输入数据很多,请用scanf而不是cin 

输入说明 

这里有3只奶牛和10个时间段cow #1 能在时间段1..7工作, cow #2 能在时间段3..6工作, cow #3 能在时间段6..10工作 

输出说明: 

选择 cows #1 和 #3即可,没有更优的方案了 .
 
  思路:仍旧采用贪心的解法 ,选取最优解。为了使用最小的牛覆盖所有时间段 ,就要使用开始的早,工作时间长的牛(具体实现使用cmp排序,优先级高的是开始时间,开始时间相同时比较结束时间,结束时间晚的优先);还要考虑一点即是所有牛的工作时间段
需要覆盖整个T时间段,中间不能有空缺(可以进行循环比较,当循环到某个牛该牛的工作开始时间比上一个工作的牛的结束时间相等或大于的时候,跳出循环)。代码如下:
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <queue>
#include <map>
#include <stack>
#include <utility>
#define LL long long
int const max_n = 25100;
using namespace std;

struct node{
    int a,b;
}num[max_n];

bool cmp(node x,node y)//排序函数
{
    if(x.a==y.a)return x.b>y.b;
    else return x.a<y.a;
}

int main()
{
    int n,t;
    scanf("%d %d",&n,&t);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&num[i].a,&num[i].b);
    }
    sort(num,num+n,cmp);
    int end=0,begin=0,sum=0;//结束时间,开始时间,计数器
    bool judge=false;
    for(int i=0;i<n;i++)
    {
        bool tt=false;//因为后面循环体内,在给结束时间赋值后,i又加了一次,所以跳出循环的i比实际牛的小标大一,在后面进行-1处理
        while(num[i].a<=begin+1&&i<n)//判断是否覆盖到了所有的时间段,如果中间出现时间断了的情况,则end值不会更新,导致begin值不会更新,每一个后来的牛的开始时间都将大于begin时间,这样在for循环内的if(begin>=t)不会执行,从而得出不能搬办到的结果。
        {
            tt=true;
            end=max(end,num[i].b);
            i++;
        }
        begin=end;
        sum++;
        if(tt)i--;
        if(begin>=t){
            judge=true;
            break;
        }
    }
    if(judge)printf("%d\n",sum);//只有工作时间覆盖所有时间段,且最后一头牛的结束时间大于总时间t时,输出使用的牛的数量
    else printf("-1\n");
    return 0;
}

 

贪心算法小结

原文:https://www.cnblogs.com/whocarethat/p/11031355.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!