POJ 2010 Moo University - Financial Aid

    先将序列以score排序，于是有一个以financial aid的值的序列。

    于是可以枚举每一个点为中位数点，那么要满足题目条件则有：

    选择第i个点位中位数点，那么设i点之前的(n / 2)个financial aid 为 dp1[i - 1],设i点之后的(n / 2)个financial aid为dp2[i + 1]

    则有 F[i](i点的financial aid值） + dp1[i - 1] + dp2[i + 1] <= F 的时候，满足条件

    由于序列是以score递增的，从小到大扫一遍可以得到答案，只需O(n)

    那么如何确定dp1[]和dp2[]呢

    分别维护一个最大堆，初始的时候最大堆的元素的数目为(n / 2) 个，那么每次更新一个点的时候，若这个点的F > 最大堆堆顶点的F，那么更新dp[]值

    于是只需要log(n)的时间来维护这个dp值，故总的复杂度为O(nlogn);

    贴上我的堆模板

 

1 #include < iostream >
2 #include < algorithm >
3
4   using namespace std;
5
6   /*
7 MAX_HEAP = 1的时候为最大堆 MAX_HEAP = 0为最小堆
8 HEAP_SIZE 为堆的元素个数的最大值
9 push()为传入一个元素给堆
10 top()取堆顶元素，并且删掉该元素
11 初始化堆的时候注意 heap_size = 0
12 若同时操作最大堆最小堆，可以将MAX_HEAP放入struct中并标记
13 */
14 #define HEAP_SIZE 200000
15 #define MAX_HEAP 1
16 struct HEAP
17 {
18 int heap[ HEAP_SIZE ], heap_size;
19 void push( int k) {
20 heap[ heap_size ++ ] = k;
21 int c = heap_size - 1 ;
22 while ((c >> 1 ) >= 0 ) {
23 if (MAX_HEAP ? (heap[c >> 1 ] < heap[c])
24 : (heap[c >> 1 ] > heap[c]) )
25 swap(heap[c] , heap[c >> 1 ]);
26 else break ;
27 c >>= 1 ;
28 }
29 }
30 int top() {
31 int ret = heap[ 0 ], c = 0 , son;
32 heap[ 0 ] = heap[ -- heap_size ];
33 while ((c << 1 ) < heap_size) {
34 if (c) son = (c << 1 ); else son = 1 ;
35 if (son + 1 < heap_size && (MAX_HEAP ? (heap[ son + 1 ] > heap[ son ])
36 : (heap[ son + 1 ] < heap[ son ]) )
37 ) son ++ ;
38 if (MAX_HEAP ? (heap[c] < heap[son]) : (heap[c] > heap[son]) )
39 swap(heap[son], heap[c]);
40 else break ;
41 c = son;
42 }
43 return ret;
44 }
45 };
46
47 HEAP hp;
48 #define maxn 200000
49 int n, c, f, dp1[ maxn ], dp2[ maxn ];
50 struct node { int si, fi; } men[ maxn ];
51
52 bool cmp( const node S, const node T) {
53 return S.si < T.si;
54 }
55
56 void solve()
57 {
58 int i, j, k;
59
60 hp.heap_size = 0 ;
61 for (i = 0 ; i < (n >> 1 ); i ++ )
62 {
63 dp1[ (n >> 1 ) - 1 ] += men[i].fi;
64 hp.push( men[i].fi );
65 }
66 for (i = (n >> 1 ); i < c; i ++ )
67 {
68 if (hp.heap[ 0 ] > men[i].fi) {
69 dp1[i] = dp1[i - 1 ] - hp.top();
70 dp1[i] += men[i].fi;
71 hp.push( men[i].fi );
72 } else dp1[i] = dp1[i - 1 ];
73 }
74
75 hp.heap_size = 0 ;
76 for (i = c - 1 ; i >= (c - (n >> 1 )); i -- )
77 {
78 dp2[ (c - (n >> 1 )) ] += men[i].fi;
79 hp.push( men[i].fi );
80 }
81 for (i = (c - (n >> 1 ) - 1 ); i >= 0 ; i -- )
82 {
83 if (hp.heap[ 0 ] > men[i].fi) {
84 dp2[i] = dp2[i + 1 ] - hp.top();
85 dp2[i] += men[i].fi;
86 hp.push( men[i].fi );
87 } else dp2[i] = dp2[i + 1 ];
88 }
89 }
90
91 int main()
92 {
93 int i, j, k;
94 memset(dp1, 0 , sizeof (dp1));
95 memset(dp2, 0 , sizeof (dp2));
96
97 scanf( " %d %d %d " , & n, & c, & f);
98 for (i = 0 ; i < c; i ++ )
99 scanf( " %d %d " , & men[i].si, & men[i].fi);
100 sort(men, men + c, cmp);
101
102 if (n != 1 )
103 solve();
104
105 int ans = - 1 ;
106 for (i = (n >> 1 ); i <= (c - (n >> 1 ) - 1 ); i ++ )
107 if (dp1[i - 1 ] + dp2[i + 1 ] + men[i].fi <= f)
108 ans = men[i].si;
109
110 printf( " %d\n " , ans);
111 // system("pause");
112 return 0 ;
113 }
114
115