题目大意:有n个奶牛,他们负责在长为t个时间点的时间内值班,每个时间点至少有一个在值班,每个奶牛有一段空闲时间可以值班,求满足要求所需最少奶牛数量,无法满足则输出-1.

分析:

将奶牛空闲时间段看成线段,按线段左端点进行排序,排序后从第一个线段开始,每次选择与前一个线段有重合或恰好相接的线段,并在满足此条件同时选择右端点最大的,让该奶牛值班。在选择时要避免选择线段右端点比前一个选择的线段右端点还小或相等的情况,注意处理好首尾线段即可。

代码:

program cleaning;
var
a,b:array[..]of longint;
n,i,m,j,k,t,g,p:longint;
procedure qsort(l,h:longint);
var i,j,t,m:longint;
begin i:=l; j:=h;
m:=a[(i+j) div ];
repeat
while a[i]<m do inc(i);
while m<a[j] do dec(j);
if i<=j then
begin t:=a[i]; a[i]:=a[j]; a[j]:=t; t:=b[i]; b[i]:=b[j]; b[j]:=t;
inc(i); dec(j); end; until i>j;
if i<h then qsort(i,h); if j>l then qsort(l,j); end;
begin
assign(input,'cleaning.in');
reset(input);
assign(output,'cleaning.out');
rewrite(output);
readln(n,t);
for i:= to n do
read(a[i],b[i]);
qsort(,n);
k:=;
for i:= to n do
begin
if a[i]<=k then if (b[i]>m)and(b[i]>=p) then m:=b[i];
if a[i]>k then if a[i]>m+ then begin writeln(-); break; end else begin k:=m+;p:=k; j:=j+; if m>=t then begin g:=; break; end; m:=b[i];end;
end;
if m>=t then if g= then writeln(j+) else writeln(j) else if i=n then writeln(-);
close(input); close(output);
end.

最新文章

  1. Codeforces 732D [二分 ][贪心]
  2. python mysql
  3. Codeforces Round #110 (Div. 2)
  4. 38-语言入门-38-Coin Test
  5. SCP和SFTP(转)
  6. JAva Collections类方法详解
  7. 【转】Java线程与Linux内核线程的映射关系
  8. react系列笔记:第三记-redux-saga
  9. [转]Nginx 静态资源缓存设置
  10. mysql在查询中常见问题汇总
  11. easyui,文件引用
  12. 微信小程序--getLocation需要在app.json中声明permission字段
  13. inline详解
  14. Java集合入门
  15. [ACM_数据结构] HDU 1166 敌兵布阵 线段树 或 树状数组
  16. 定时任务crone表达式demo
  17. freetype 编译
  18. 第三次作业 史浩然 -assassin Talon
  19. IOS UITableView删除功能
  20. “全栈2019”Java第二十九章:数组详解(中篇)

热门文章

  1. UVA 12166 Equilibrium Mobile(贪心,反演)
  2. Spark的基本概念及工作原理
  3. python_16_自己建立模块
  4. Java Web Application使Session永不失效(利用cookie隐藏登录)
  5. Bootstrap 提示工具(Tooltip)插件的事件
  6. sql注入问题 java中将MySQL的数据库验证秘密加上 &#39; or &#39;1&#39;= &#39;1 就可以出现万能密码
  7. 理解Express 中间件
  8. AngularJS1.X版本双向绑定九问
  9. GNU C中__attribute__
  10. 七、Linux 文件与目录管理