51nod_learn_greedy_活动安排2
有若干个活动，第i个开始时间和结束时间是[Si,fi)，同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？
第一行一个正整数n (n <= 10000)代表活动的个数。
第二行到第(n + 1)行包含n个开始时间和结束时间。
开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000
输出
一行包含一个整数表示最少教室的个数。
输入示例
3
1 2
3 4
2 9
输出示例
2<br></br><br></br><br></br>其实就是求某个时间点的最大厚度...<br></br>一开始傻逼了...<br></br>想着什么从１开始推过去...必然tle．．就没写＝＝<br></br>然后今天再开...我只要把开始时间和结束时间放在一起排序...从小到大<br></br>然后用一个boolean做好标记就好...<br></br>有点像海洋兄的收费站的比喻？
1<span style="color: #008080;"> 1</span> <span style="color: #008000;">/*</span><span style="color: #008000;">************************************************************************
2</span><span style="color: #008080;"> 2</span> <span style="color: #008000;"> > File Name: code/51nod/learn/greedy/2.cpp
3</span><span style="color: #008080;"> 3</span> <span style="color: #008000;"> > Author: 111qqz
4</span><span style="color: #008080;"> 4</span> <span style="color: #008000;"> > Email: rkz2013@126.com
5</span><span style="color: #008080;"> 5</span> <span style="color: #008000;"> > Created Time: 2015年10月05日 星期一 19时24分32秒
6</span><span style="color: #008080;"> 6</span> <span style="color: #008000;"> ***********************************************************************</span><span style="color: #008000;">*/</span>
7<span style="color: #008080;"> 7</span>
8<span style="color: #008080;"> 8</span> #include<iostream>
9<span style="color: #008080;"> 9</span> #include<iomanip>
10<span style="color: #008080;">10</span> #include<cstdio>
11<span style="color: #008080;">11</span> #include<algorithm>
12<span style="color: #008080;">12</span> #include<cmath>
13<span style="color: #008080;">13</span> #include<cstring>
14<span style="color: #008080;">14</span> #include<<span style="color: #0000ff;">string</span>>
15<span style="color: #008080;">15</span> #include<map>
16<span style="color: #008080;">16</span> #include<<span style="color: #0000ff;">set</span>>
17<span style="color: #008080;">17</span> #include<queue>
18<span style="color: #008080;">18</span> #include<vector>
19<span style="color: #008080;">19</span> #include<stack>
20<span style="color: #008080;">20</span> #include<cctype>
21<span style="color: #008080;">21</span>
22<span style="color: #008080;">22</span> <span style="color: #0000ff;">#define</span> yn hez111qqz
23<span style="color: #008080;">23</span> <span style="color: #0000ff;">#define</span> j1 cute111qqz
24<span style="color: #008080;">24</span> <span style="color: #0000ff;">#define</span> ms(a,x) memset(a,x,sizeof(a))
25<span style="color: #008080;">25</span> <span style="color: #0000ff;">using</span> <span style="color: #0000ff;">namespace</span><span style="color: #000000;"> std;
26</span><span style="color: #008080;">26</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> dx4[<span style="color: #800080;">4</span>]={<span style="color: #800080;">1</span>,<span style="color: #800080;">0</span>,<span style="color: #800080;">0</span>,-<span style="color: #800080;">1</span><span style="color: #000000;">};
27</span><span style="color: #008080;">27</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> dy4[<span style="color: #800080;">4</span>]={<span style="color: #800080;">0</span>,-<span style="color: #800080;">1</span>,<span style="color: #800080;">1</span>,<span style="color: #800080;">0</span><span style="color: #000000;">};
28</span><span style="color: #008080;">28</span> typedef <span style="color: #0000ff;">long</span> <span style="color: #0000ff;">long</span><span style="color: #000000;"> LL;
29</span><span style="color: #008080;">29</span> typedef <span style="color: #0000ff;">double</span><span style="color: #000000;"> DB;
30</span><span style="color: #008080;">30</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> inf = <span style="color: #800080;">0x3f3f3f3f</span><span style="color: #000000;">;
31</span><span style="color: #008080;">31</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> N=1E4+<span style="color: #800080;">5</span><span style="color: #000000;">;
32</span><span style="color: #008080;">32</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> n;
33</span><span style="color: #008080;">33</span> <span style="color: #0000ff;">struct</span><span style="color: #000000;"> Q
34</span><span style="color: #008080;">34</span> <span style="color: #000000;">{
35</span><span style="color: #008080;">35</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> t;
36</span><span style="color: #008080;">36</span> <span style="color: #0000ff;">bool</span><span style="color: #000000;"> sta;
37</span><span style="color: #008080;">37</span> }q[<span style="color: #800080;">2</span>*<span style="color: #000000;">N];
38</span><span style="color: #008080;">38</span>
39<span style="color: #008080;">39</span> <span style="color: #0000ff;">bool</span><span style="color: #000000;"> cmp(Q a,Q b)
40</span><span style="color: #008080;">40</span> <span style="color: #000000;">{
41</span><span style="color: #008080;">41</span> <span style="color: #0000ff;">return</span> a.t<<span style="color: #000000;">b.t;
42</span><span style="color: #008080;">42</span> <span style="color: #000000;">}
43</span><span style="color: #008080;">43</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> main()
44</span><span style="color: #008080;">44</span> <span style="color: #000000;">{
45</span><span style="color: #008080;">45</span> <span style="color: #000000;"> #ifndef ONLINE_JUDGE
46</span><span style="color: #008080;">46</span> freopen(<span style="color: #800000;">"</span><span style="color: #800000;">in.txt</span><span style="color: #800000;">"</span>,<span style="color: #800000;">"</span><span style="color: #800000;">r</span><span style="color: #800000;">"</span><span style="color: #000000;">,stdin);
47</span><span style="color: #008080;">47</span> <span style="color: #0000ff;">#endif</span>
48<span style="color: #008080;">48</span>
49<span style="color: #008080;">49</span> scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%d</span><span style="color: #800000;">"</span>,&<span style="color: #000000;">n);
50</span><span style="color: #008080;">50</span> <span style="color: #0000ff;">for</span> ( <span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span> ; i < <span style="color: #800080;">2</span>*n ; i++<span style="color: #000000;">)
51</span><span style="color: #008080;">51</span> <span style="color: #000000;"> {
52</span><span style="color: #008080;">52</span> scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%d</span><span style="color: #800000;">"</span>,&<span style="color: #000000;">q[i].t);
53</span><span style="color: #008080;">53</span> <span style="color: #0000ff;">if</span> (i%<span style="color: #800080;">2</span>==<span style="color: #800080;">0</span><span style="color: #000000;">)
54</span><span style="color: #008080;">54</span> <span style="color: #000000;"> {
55</span><span style="color: #008080;">55</span> q[i].sta = <span style="color: #0000ff;">true</span><span style="color: #000000;">;
56</span><span style="color: #008080;">56</span> <span style="color: #000000;"> }
57</span><span style="color: #008080;">57</span> <span style="color: #0000ff;">else</span>
58<span style="color: #008080;">58</span> <span style="color: #000000;"> {
59</span><span style="color: #008080;">59</span> q[i].sta = <span style="color: #0000ff;">false</span><span style="color: #000000;">;
60</span><span style="color: #008080;">60</span> <span style="color: #000000;"> }
61</span><span style="color: #008080;">61</span> <span style="color: #000000;"> }
62</span><span style="color: #008080;">62</span> sort(q,q+<span style="color: #800080;">2</span>*<span style="color: #000000;">n,cmp);
63</span><span style="color: #008080;">63</span> <span style="color: #0000ff;">int</span> ans = -<span style="color: #800080;">1</span><span style="color: #000000;">;
64</span><span style="color: #008080;">64</span> <span style="color: #0000ff;">int</span> cnt = <span style="color: #800080;">0</span><span style="color: #000000;">;
65</span><span style="color: #008080;">65</span> <span style="color: #0000ff;">for</span> ( <span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span> ; i < <span style="color: #800080;">2</span>*n ; i++<span style="color: #000000;">)
66</span><span style="color: #008080;">66</span> <span style="color: #000000;"> {
67</span><span style="color: #008080;">67</span> <span style="color: #0000ff;">if</span><span style="color: #000000;"> (q[i].sta)
68</span><span style="color: #008080;">68</span> <span style="color: #000000;"> {
69</span><span style="color: #008080;">69</span> cnt++<span style="color: #000000;">;
70</span><span style="color: #008080;">70</span> <span style="color: #000000;"> }
71</span><span style="color: #008080;">71</span> <span style="color: #0000ff;">else</span>
72<span style="color: #008080;">72</span> <span style="color: #000000;"> {
73</span><span style="color: #008080;">73</span> cnt--<span style="color: #000000;">;
74</span><span style="color: #008080;">74</span> <span style="color: #000000;"> }
75</span><span style="color: #008080;">75</span> ans =<span style="color: #000000;"> max(ans,cnt);
76</span><span style="color: #008080;">76</span> <span style="color: #000000;"> }
77</span><span style="color: #008080;">77</span> printf(<span style="color: #800000;">"</span><span style="color: #800000;">%dn</span><span style="color: #800000;">"</span><span style="color: #000000;">,ans);
78</span><span style="color: #008080;">78</span>
79<span style="color: #008080;">79</span>
80<span style="color: #008080;">80</span> <span style="color: #000000;"> #ifndef ONLINE_JUDGE
81</span><span style="color: #008080;">81</span> <span style="color: #000000;"> fclose(stdin);
82</span><span style="color: #008080;">82</span> <span style="color: #0000ff;">#endif</span>
83<span style="color: #008080;">83</span> <span style="color: #0000ff;">return</span> <span style="color: #800080;">0</span><span style="color: #000000;">;
84</span><span style="color: #008080;">84</span> }
View Code
<br></br>