Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 102 Solved: 46
一天有T(1≤T≤10^6)个时段.约翰正打算安排他的N(1≤N≤25000)只奶牛来值班,打扫
打扫牛棚卫生.每只奶牛都有自己的空闲时间段[Si,Ei](1≤Si≤Ei≤T),只能把空闲的奶牛安排出来值班.而且,每个时间段必需有奶牛在值班. 那么,最少需要动用多少奶牛参与值班呢?如果没有办法安排出合理的方案,就输出-1.
第1行:N,T.
第2到N+1行:Si,Ei.
最少安排的奶牛数.
3 10 1 7 3 6 6 10
2 样例说明 奶牛1和奶牛3参与值班即可.
题解:这道题做法有很多,比如:DP(虽然多半会TLE)、贪心、甚至最短路
DP:不用多说,就是通过各个区间进行对于前面的转移,所以需要用到一个快速的区间查询数据结构进行维护,但是很可惜,时限是1s,而T<=1000000,TLE是十有八九的事
贪心:显然,对于多个结束时间相同的区间来说,保留一个起始时间最长的即可,于是我们开始进行贪心
1 /**************************************************************
2 Problem: 3389
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:100 ms
7 Memory:1008 kb
8 ****************************************************************/
9
10 var
11 i,j,k,l,m,n,ans:longint;
12 a:array[0..100000,1..2] of longint;
13 function max(x,y:longint):longint;
14 begin
15 if x>y then max:=x else max:=y;
16 end;
17 procedure swap(var x,y:longint);
18 var z:longint;
19 begin
20 z:=x;x:=y;y:=z;
21 end;
22
23 procedure sort(l,r:longint);
24 var i,j,x,y:longint;
25 begin
26 i:=l;j:=r;x:=a[(l+r) div 2,1];y:=a[(l+r) div 2,2];
27 repeat
28 while (a[i,1]<x) or ((a[i,1]=x) and (a[i,2]<y)) do inc(i);
29 while (a[j,1]>x) or ((a[j,1]=x) and (a[j,2]>y)) do dec(j);
30 if i<=j then
31 begin
32 swap(a[i,1],a[j,1]);
33 swap(a[i,2],a[j,2]);
34 inc(i);dec(j);
35 end;
36 until i>j;
37 if i<r then sort(i,r);
38 if l<j then sort(l,j);
39 end;
40 begin
41 readln(n,m);
42 a[0,1]:=0;a[0,2]:=0;
43 for i:=1 to n do readln(a[i,1],a[i,2]);
44 sort(1,n);ans:=0;
45 while l<m do
46 begin
47 j:=l;
48 while (k<n) and (a[k+1,1]<=(j+1)) do
49 begin
50 inc(k);
51 l:=max(l,a[k,2]);
52 end;
53 if (k=n) and (a[k,2]<m) or (a[k+1,1]>(l+1)) then
54 begin
55 writeln(-1);
56 halt;
57 end;
58 inc(ans);
59 end;
60 if l<m then writeln(-1) else writeln(ans);
61 end.
最短路:这道题个人认为最神奇的做法就是最短路,我们可以以每个时间点为节点,对于所有的(i,i-1)连边权为0的有向边,对于数据所给的时间段(x,y),连(x-1,y)边权为1的有向边,然后求0到T的最短路即可,还有——对于P党来说一个很大的重点在于离散化,必须把一些只指向前一个节点而且边权还为0的给压缩,这样子可以节省大量时间,我原来简单的最短路居然TLE,离散化之后就AC了(HansBug:感谢phile神犇的离散化点子么么哒)
1 /**************************************************************
2 Problem: 3389
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:160 ms
7 Memory:5132 kb
8 ****************************************************************/
9
10 type
11 point=^node;
12 node=record
13 g,w:longint;
14 next:point;
15 end;
16 var
17 i,j,k,l,m,n,f,r:longint;
18 a,b:array[0..60000,1..3] of longint;
19 c,g:array[0..50000] of longint;
20 d:array[0..500000] of longint;
21 e:array[0..50000] of point;
22 p:point;
23 procedure add(x,y,z:longint);
24 var p:point;
25 begin
26 new(p);p^.g:=y;p^.w:=z;p^.next:=e[x];e[x]:=p;
27 end;
28 procedure swap(var x,y:longint);
29 var z:longint;
30 begin
31 z:=x;x:=y;y:=z;
32 end;
33 procedure sort(l,r:longint);
34 var i,j,x,y:longint;
35 begin
36 i:=l;j:=r;x:=b[(l+r) div 2,1];
37 repeat
38 while b[i,1]<x do inc(i);
39 while b[j,1]>x do dec(j);
40 if i<=j then
41 begin
42 swap(b[i,1],b[j,1]);
43 swap(b[i,2],b[j,2]);
44 swap(b[i,3],b[j,3]);
45 inc(i);dec(j);
46 end;
47 until i>j;
48 if i<r then sort(i,r);
49 if l<j then sort(l,j);
50 end;
51
52 begin
53 readln(n,m);
54 for i:=1 to n do
55 begin
56 readln(a[i,1],a[i,2]);a[i,1]:=a[i,1]-1;
57 b[i*2-1,1]:=a[i,1];b[i*2-1,2]:=i;b[i*2-1,3]:=1;
58 b[i*2,1]:=a[i,2];b[i*2,2]:=i;b[i*2,3]:=2;
59 end;
60 b[n*2+1,1]:=m;b[n*2+1,2]:=0;b[n*2+1,3]:=0;
61 sort(1,n*2);
62 b[0,1]:=0;
63 for i:=1 to n*2 do
64 begin
65 if b[i,1]<>b[i-1,1] then inc(j);
66 a[b[i,2],b[i,3]]:=j;
67 end;
68 if b[n*2+1,1]>b[n*2,1] then inc(j);
69 m:=j;
70 for i:=0 to m do e[i]:=nil;
71 for i:=m downto 1 do add(i,i-1,0);
72 for i:=1 to n do add(a[i,1],a[i,2],1);
73 fillchar(c,sizeof(c),0);fillchar(g,sizeof(g),0);
74 c[0]:=1;d[1]:=0;f:=1;r:=2;g[0]:=1;
75 while f<r do
76 begin
77 p:=e[d[f]];
78 while p<>nil do
79 begin
80 if (c[p^.g]=0) or (c[p^.g]>(c[d[f]]+p^.w)) then
81 begin
82 c[p^.g]:=c[d[f]]+p^.w;
83 if g[p^.g]=0 then
84 begin
85 g[p^.g]:=1;
86 d[r]:=p^.g;
87 inc(r);
88 end;
89 end;
90 p:=p^.next;
91 end;
92 inc(f);
93 g[d[f]]:=0;
94 end;
95 for i:=0 to m do dec(c[i]);
96 writeln(c[m]);
97 readln;
98 end.