专栏首页HansBug's Lab3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者

3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者

3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者

Time Limit: 3 Sec  Memory Limit: 128 MB

Submit: 71  Solved: 62

[Submit][Status][Discuss]

Description

    约翰有N(1≤N≤50000)头牛,约翰的草地可以认为是一条直线.每只牛只喜欢在某个特定的范围内吃草.第i头牛喜欢在区间(Si,Ei)吃草,1≤Si<Ei≤1,000,000,00.

    奶牛们都很自私,他们不喜欢和其他奶牛共享自己喜欢吃草的领域,因此约翰要保证任意

两头牛都不会共享他们喜欢吃草昀领域.如果奶牛i和奶牛J想要同时吃草,那么要满足:Si>=Ej或者Ei≤Sj.约翰想知道在同一时刻,最多可以有多少头奶牛同时吃草?

Input

    第1行:一个整数N.

    第2到N+1行:第i+l行有两个整数Si,Ei.

Output

    一个整数,最多可以有多少头牛同时吃草.

Sample Input

5 2 4 1 12 4 5 7 10 7 8

Sample Output

3

HINT

  第1,3,4共3只奶牛可以同时吃草,第1,3,5也可以.

Source

Silver

题解:贪心水题一道= =。。。很明显对于同样的右界限区间,显然选范围最小的肯定没有错,于是只保留范围小的,然后排序,贪心水过。。。

 1 /**************************************************************
 2     Problem: 3410
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:212 ms
 7     Memory:696 kb
 8 ****************************************************************/
 9  
10 var
11    i,j,k,l,m,n,t:longint;
12    a:array[0..60000,1..2] of longint;
13 procedure swap(var x,y:longint);
14           var z:longint;
15           begin
16                z:=x;x:=y;y:=z;
17           end;
18 procedure sort(l,r:longint);
19           var i,j,x,y:longint;
20           begin
21                i:=l;j:=r;x:=a[(l+r) div 2,2];y:=a[(l+r) div 2,1];
22                repeat
23                      while (a[i,2]<x) or ((a[i,2]=x) and (a[i,1]>y)) do inc(i);
24                      while (a[j,2]>x) or ((a[j,2]=x) and (a[j,1]<y)) do dec(j);
25                      if i<=j then
26                         begin
27                              swap(a[i,1],a[j,1]);
28                              swap(a[i,2],a[j,2]);
29                              inc(i);dec(j);
30                         end;
31                until i>j;
32                if i<r then sort(i,r);
33                if l<j then sort(l,j);
34           end;
35 begin
36      readln(n);
37      for i:=1 to n do readln(a[i,1],a[i,2]);
38      sort(1,n);
39      a[0,1]:=0;a[0,2]:=0;
40      t:=0;l:=0;
41      for i:=1 to n do
42          if a[i,2]<>a[i-1,2] then
43             if a[i,1]>=t then
44                begin
45                     t:=a[i,2];
46                     inc(l);
47                end;
48      writeln(l);
49      readln;
50 end.     

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2243: [SDOI2011]染色

    2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MB Submit: 3113  Solved...

    HansBug
  • 2929: [Poi1999]洞穴攀行

    2929: [Poi1999]洞穴攀行 Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 80  Solved: ...

    HansBug
  • 1622: [Usaco2008 Open]Word Power 名字的能量

    1622: [Usaco2008 Open]Word Power 名字的能量 Time Limit: 5 Sec  Memory Limit: 64 MB Su...

    HansBug
  • 1339 / 1163: [Baltic2008]Mafia

    1163: [Baltic2008]Mafia Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 96  Sol...

    HansBug
  • 1622: [Usaco2008 Open]Word Power 名字的能量

    1622: [Usaco2008 Open]Word Power 名字的能量 Time Limit: 5 Sec  Memory Limit: 64 MB Su...

    HansBug
  • 3401: [Usaco2009 Mar]Look Up 仰望

    3401: [Usaco2009 Mar]Look Up 仰望 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: ...

    HansBug
  • 1934: [Shoi2007]Vote 善意的投票

    1934: [Shoi2007]Vote 善意的投票 Time Limit: 1 Sec  Memory Limit: 64 MB Submit: 1174  ...

    HansBug
  • 算法模板——线段树3(区间覆盖值+区间求和)

    实现功能——1:区间覆盖值;2:区间求和 相比直接的区间加,这个要注重顺序,因为操作有顺序之分。所以这里面的tag应该有个pushup操作(本程序中的ext) ...

    HansBug
  • 算法模板——线段树5(区间开根+区间求和)

    实现功能——1:区间开根;2:区间求和(此模板以BZOJ3038为例) 作为一个非常规的线段树操作,其tag也比较特殊呵呵哒 1 var 2 i,j,...

    HansBug
  • 2243: [SDOI2011]染色

    2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MB Submit: 3113  Solved...

    HansBug

扫码关注云+社区

领取腾讯云代金券