博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【BZOJ】3389: [Usaco2004 Dec]Cleaning Shifts安排值班(贪心)
阅读量:6755 次
发布时间:2019-06-26

本文共 1568 字,大约阅读时间需要 5 分钟。

显然左端点排序后,依次取。

要考虑下一次取的方案:

待选点为a[j].x<=a[now].y+1的所有点j,其中now是当前所选

那么我们要在这些点内做决策

贪心就是取y最大的待选点,即

max(a[j].y)的j

实现中细节太多QAQ,写了挺久的。。

#include 
#include
#include
#include
#include
#include
#include
using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << #x << " = " << x << endl#define printarr2(a, b, c) for1(i, 1, b) { for1(j, 1, c) cout << a[i][j]; cout << endl; }#define printarr1(a, b) for1(i, 1, b) cout << a[i]; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a
1) { puts("-1"); return 0; } int ans=1, now=1; for1(i, 1, cnt) { int fix=0, nx=now, pos=0, ed=a[now].y; while(nx
ed && fix

 

 


 

 

Description

    一天有T(1≤T≤10^6)个时段.约翰正打算安排他的N(1≤N≤25000)只奶牛来值班,打扫
打扫牛棚卫生.每只奶牛都有自己的空闲时间段[Si,Ei](1≤Si≤Ei≤T),只能把空闲的奶牛安排出来值班.而且,每个时间段必需有奶牛在值班.  那么,最少需要动用多少奶牛参与值班呢?如果没有办法安排出合理的方案,就输出-1.

Input

 
    第1行:N,T.
    第2到N+1行:Si,Ei.

Output

 
    最少安排的奶牛数.

Sample Input

3 10
1 7
3 6
6 10

Sample Output

2
样例说明
奶牛1和奶牛3参与值班即可.

HINT

Source

 

转载地址:http://negho.baihongyu.com/

你可能感兴趣的文章
jive论坛
查看>>
[Android问答] ListView如何加载远程图片?(附代码)
查看>>
android 调试源码
查看>>
k-means clustering - Wikipedia, the free encyclopedia
查看>>
三星S6D1121主控彩屏(240*320*18bit,262K)图形设备接口(GDI)实现
查看>>
head first java 01 ( 1 ~ 3 章 )
查看>>
Superhero.js – 构建大型 JavaScript 应用程序的最佳资源
查看>>
什么是UAT测试?
查看>>
FireDAC 下的 Sqlite [8] - 自定义函数
查看>>
Android 驱动测试程序H-M-S <2>
查看>>
Swift语言指南(七)--语言基础之布尔值和类型别名
查看>>
Hadoop 安装记录
查看>>
hdu 5206 Four Inages Strategy 判断是否是正方形
查看>>
Linq中使用Left Join
查看>>
HDFS Safemode问题
查看>>
GDI编程小结
查看>>
(C#基础) byte[] 之初始化, 赋值,转换。(转)
查看>>
mysql设置指定ip远程访问连接实例
查看>>
从js的repeat方法谈js字符串与数组的扩展方法
查看>>
IIS中添加MIME类型
查看>>