这一题如果把时间区间去掉,那就变成装箱子问题了(装箱子要用Splay维护),但是现在规定了区间和时间,我们只用贪婪算法就可以了,每次只用找到最小就可以了(用堆维护)。
1 #include
2 #include
3 #include
4
5 using namespace std;
6
7 typedef struct iterval
8 {
9 int cows_num;
10 int Which_Stall;
11 int start;
12 int end;
13 }Cow;
14 typedef struct box
15 {
16 int box_num;
17 int min_t;
18 }Stall;
19 typedef int Position;
20 int fcomp1(const void *a, const void *b)
21 {
22 return (*(Cow *)a).start - (*(Cow *)b).start;
23 }
24 int fcomp2(const void *a, const void *b)
25 {
26 return (*(Cow *)a).cows_num - (*(Cow *)b).cows_num;
27 }
28
29 static Cow cows_set[50000];
30 static Stall s_heap[50001];
31 static int sum_of_stalls;
32
33 void Search(const int);
34 void Insert(Stall, Position);
35 Stall Delete_Min(void);
36
37 int main(void)//这一题用堆维护
38 {
39 int n;
40 while (~scanf("%d", &n))
41 {
42 for (int i = 0; i )
43 {
44 scanf("%d%d", &cows_set[i].start, &cows_set[i].end);
45 cows_set[i].cows_num = i;
46 }
47 qsort(cows_set, n, sizeof(Cow), fcomp1);
48 Search(n);
49 }
50 return 0;
51 }
52
53 void Insert(Stall goal, Position pos)
54 {
55 Position s = pos, pr;
56
57 for (; s > 1; s = pr)//上滤
58 {
59 pr = s % 2 == 0 ? s >> 1 : (s - 1) >> 1;
60 if (s_heap[pr].min_t > goal.min_t)
61 s_heap[s] = s_heap[pr];
62 else break;
63 }
64 s_heap[s] = goal;
65 }
66
67 Stall Delete_Min(void)
68 {
69 Stall mins_stalls = s_heap[1],tmp = s_heap[sum_of_stalls--];
70 Position pr, s1, s2;
71
72 for (pr = 1; pr <= sum_of_stalls;)
73 {
74 s1 = pr <<1; s2 = s1 + 1;
75 if (s2 <= sum_of_stalls)
76 {
77 if (s_heap[s1].min_t < s_heap[s2].min_t){
78 s_heap[pr] = s_heap[s1]; pr = s1;
79 }
80 else{
81 s_heap[pr] = s_heap[s2]; pr = s2;
82 }
83 }
84 else
85 {
86 if (s1 <= sum_of_stalls){
87 s_heap[pr] = s_heap[s1]; pr = s1;
88 }
89 break;
90 }
91 }
92 Insert(tmp, pr);
93 return mins_stalls;
94 }
95
96 void Search(const int n)
97 {
98 Stall tmp;
99 sum_of_stalls = 1;
100 tmp.box_num = 1; tmp.min_t = cows_set[0].end;
101 Insert(tmp, 1);
102 cows_set[0].Which_Stall = 1;
103
104 for (int i = 1; i )
105 {
106 if (cows_set[i].start <= s_heap[1].min_t)//放不下
107 {
108 tmp.box_num = ++sum_of_stalls; tmp.min_t = cows_set[i].end;
109 Insert(tmp, sum_of_stalls);
110 cows_set[i].Which_Stall = sum_of_stalls;
111 }
112 else
113 {
114 tmp = Delete_Min();
115 tmp.min_t = cows_set[i].end;
116 cows_set[i].Which_Stall = tmp.box_num;
117 Insert(tmp, ++sum_of_stalls);
118 }
119 }
120 printf("%d\n", sum_of_stalls);
121 qsort(cows_set, n, sizeof(Cow), fcomp2);
122 for (int i = 0; i )
123 printf("%d\n", cows_set[i].Which_Stall);
124 }