先将高度值离散，映射到小范围，然后统计每个高度到下一个高度之间的总容积，最后从下到上不断模拟“填水”的过程。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96 |
#include <stdio.h>#include <algorithm>using
namespace std;const
int maxN = 50001;int n, v;double
lev;int b[2*maxN], h[maxN], w[maxN], d[maxN], cx[2*maxN], cv[2*maxN];int *p[2*maxN];void
input();void
process();void
compress(int
*, int
*);int
cmp(const
void *sa, const
void *sb);void
print();int
main(){ input(); compress(b, cx); process(); print(); return
0;}void
input(){ scanf("%d", &n); for
(int i=1; i<=n; i++) { scanf("%d%d%d%d", &b[i], &h[i], &w[i], &d[i]); b[i+n] = b[i] + h[i]; } b[0] = 0;// 地板 scanf("%d", &v);}void
process(){ for
(int i=1; i<=n; i++) { int
t = i + n; int
bt = w[i] * d[i]; for
(int j=b[i]; j<b[t]; j++) { cv[j] += cx[j] * bt; } } for
(int i=0; i<=2*n && v>0; i++) { if
(v>=cv[i]) { v -= cv[i]; lev += cx[i]; } else { lev += v * 1.0 / cv[i] * cx[i]; v = 0; } }}void
compress(int
*x, int
*cx){ for
(int i=0; i<=2*n; i++) p[i] = &x[i]; qsort(p, 2*n+1, sizeof(int*), cmp); int
t = 0, pt = *p[0]; *p[0] = t; for
(int i=1; i<=2*n; i++) { if
((*p[i])!=pt) { t++; cx[t-1] = *p[i] - pt; } pt = *p[i]; *p[i] = t; }}int
cmp(const
void *sa, const
void *sb){ int
a = **(int**)sa; int
b = **(int**)sb; if
(a>b) return
1; else
return -1;}void
print(){ if
(v>0) printf("OVERFLOW\n"); else
printf("%.2lf\n", lev);} |
原文：http://www.cnblogs.com/dgzxoi/p/3562113.html