您现在的位置是:首页 > 正文

poj2376 贪心

2024-02-01 00:40:30阅读 2

 

 

如题:http://poj.org/problem?id=2376

 

Cleaning Shifts
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 12069   Accepted: 3140

Description

Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chores around the barn. He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 <= T <= 1,000,000), the first being shift 1 and the last being shift T.

Each cow is only available at some interval of times during the day for work on cleaning. Any cow that is selected for cleaning duty will work for the entirety of her interval.

Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning. If it is not possible to assign a cow to each shift, print -1.

Input

* Line 1: Two space-separated integers: N and T

* Lines 2..N+1: Each line contains the start and end times of the interval during which a cow can work. A cow starts work at the start time and finishes after the end time.

Output

* Line 1: The minimum number of cows Farmer John needs to hire or -1 if it is not possible to assign a cow to each shift.

Sample Input

3 10
1 7
3 6
6 10

Sample Output

2

Hint

This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.

INPUT DETAILS:

There are 3 cows and 10 shifts. Cow #1 can work shifts 1..7, cow #2 can work shifts 3..6, and cow #3 can work shifts 6..10.

OUTPUT DETAILS:

By selecting cows #1 and #3, all shifts are covered. There is no way to cover all the shifts using fewer than 2 cows.

Source

 

要求每一个牛可以覆盖一个区间,求出最少的牛覆盖1-T的区间。

特别注意:已覆盖区间的右端点是闭的,比如一头牛干到t=3,下一头牛可以从4开始干。WA了我半天 幸好discuss里有一组数据,不然我还以为要完全覆盖所有区间...

粗心大意怎么治..愁人

 

贪心思路:设当前已经覆盖的区间右端点now_pos,每次选择一头牛,满足左端小于now_pos,右端尽可能大...

 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

struct node
{
 int l,r;
};
node a[25005];
int N,T;
int now_pos=0;

int cmp(node &a,node &b)
{
 if(a.l!=b.l)
  return a.l<b.l;
 else
  return a.r<b.r;
}
int main()
{
// freopen("C:\\1.txt","r",stdin);
 scanf("%d%d",&N,&T);
 int i;
 for(i=0;i<N;i++)
  scanf("%d%d",&a[i].l,&a[i].r);
 sort(a,a+N,cmp);
 i=0;
 int res=0;
 while(now_pos<T&&i<N)
 {
  if(a[i].l>now_pos+1)
  {
   printf("-1\n");
   return 0;
  }
  int max=0;
  while(i<N&&a[i].l<=now_pos+1)
  {
   if(a[i].r-now_pos>max)
   {
    max=a[i].r-now_pos;
   }
    i++;
  }
  if(max!=0)
  {
  now_pos+=max;
  res++;
  }
 }
 if(now_pos>=T)
 {
  printf("%d\n",res);
 }
 else
  printf("-1\n");
 return 0;
}

 

网站文章

  • 计算机数据库原理与应用,普通高等学校计算机科学与技术应用型规划教材:数据库原理与应用...

    《数据库原理与应用》系统全面地阐述数据库系统的基础理论、基本技术和基本方法。全书共分为10章,主要介绍了数据库基础理论、关系模型、关系数据库标准语言SQL、关系数据库设计理论、数据库安全保护、数据库设...

    2024-02-01 00:40:25
  • Android模块化项目模块间数据交互解决方案

    Android模块化项目模块间数据交互解决方案

    之前呢,也做过一个关于模块化业务分离的架构方案,这篇帖子想分享一下关于模块间的数据交互的方案。模块化架构,基础的可以通过创建多个module来把业务进行区分和代码的解耦。为了解耦,让module可拆卸,可移植,那么业务模块间是不会有任何的依赖和引用的,在这样的情况下,我们如何才能让模块间联系起来,进行数据交互呢。 下面来对我项目的思路做个概述。1.涉及框架 路由框架, ...

    2024-02-01 00:40:17
  • You need to use a Theme.AppCompat theme (or descendant) with this activity. 最新发布

    You need to use a Theme.AppCompat theme (or descendant) with this activity. 最新发布

    【代码】You need to use a Theme.AppCompat theme (or descendant) with this activity.

    2024-02-01 00:39:47
  • 线性相关 线性无关

    1.线性相关(linearly dependent)与线性无关的(linearly independent)定义 线性相关的定义为: 对于一组向量v1,v2,⋯ ,vnv_1, v_2, \cdots...

    2024-02-01 00:39:39
  • 点云相关理论

    点云相关理论

    再以控制点为基站直接将扫描的多测站的点云数据与其拼接,即可将扫描的所有点云数据转换成工程实际需要的坐标系。由于目标物的复杂性,通常需要从不同方位扫描多个测站,才能把目标物扫描完整,每一测站扫描数据都有...

    2024-02-01 00:39:32
  • c语言合并k个有序链表,经典算法——合并K个有序链表(示例代码)

    c语言合并k个有序链表,经典算法——合并K个有序链表(示例代码)

    一、题目要求:将K个有序链表合并为一个有序链表二、实现方法:方法一:利用最小堆方法用一个大小为K的最小堆(用优先队列+自定义降序实现)(优先队列就是大顶堆,队头元素最大,自定义为降序后,就变成小顶堆,...

    2024-02-01 00:39:04
  • JavaScript数组

    数组1. 定义数组(array)是按次序排列的⼀组值。每个值的位置都有编号(从0开始),整个数组⽤⽅括号表⽰。var arr = ['a', 'b', 'c'];上⾯代码中的 a 、 b 、 c 就构成⼀个数组,两端的⽅括号是数组的标志。 a 是0号位置, b 是1号位置, c 是2号位置。除了在定义时赋值,数组也可以先定义后赋值。var arr = []; arr[0] = ...

    2024-02-01 00:38:58
  • AVFoundation的介绍

    AVFoundation的介绍

    一、简述 AVFoundation是一个OC媒体数据的高级框架。AVFoundation的构建考虑到了目前的硬件环境和应用程序,其设计过程高度依赖多线程机制。充分利用了多核硬件的优势并大量使用block和GCD机制,将复杂的计算机进程放到了后台线程运行。会自动提供硬件加速操作,确保在大部分设备上应用程序能以最佳性能运行。该框架就是针对64位处理器设计的,可以发挥64位处理器的所有优势。 二

    2024-02-01 00:38:50
  • excel粘贴时出现故障_Word粘贴时出现“文件未找到:MathPage.WLL”的解决方案

    excel粘贴时出现故障_Word粘贴时出现“文件未找到:MathPage.WLL”的解决方案

    问题:每次装完MathType后,在word里面进行粘贴操作时,总是出现“运行时错误‘53’:文件未找到:MathPage.WLL”。面对这种情况每次都要花点时间找真正的解决方案,然而并不是所有人提供...

    2024-02-01 00:38:43
  • 输出1~n的全排列(递归法) 热门推荐

    #include #include #include #include using namespace std; int a[1000]={0};//保存数列的数组,默认每个位置都是0 int book[1000]={0};//记录一个数有没有在数组里 int n;//1~n void A(int pos)//向a[pos]填数 { if(pos==n+1)//递归边界

    2024-02-01 00:38:14