题目链接：http://poj.org/problem?id=2010
题意：C只牛犊，各有自己的分数score和申请的补助aid，现要选出N只（N为奇数），使得其aid的总和不超过F，且按score排序后中位数最大。
数据范围：N [1, 19999], C [N, 10^5], aid [0, 10^5], F, score不超过int的最大值
思路：
1. 先将C只牛按score从小到大排序，得到序列 s，这样顺序抽取出N只构成的序列 t 必然是 s 的子序列。
中位数特殊的地方在于它在序列中所处的位置，t 的长度为N，则中位数 m 是 t 的第N/2个位置（从0开始数），因此从原序列中抽取时，要保证 m 前后都已有N/2个元素。
所以 m 的位置在原序列中是有一定范围约束的，具体分析可得范围区间[N/2, C-N/2-1]（从0开始）。
2. 既然已经按score从小到大排序，那么我们希望 m 在原序列 s 中的位置越靠后越好。因此可以在范围区间内从后往前枚举中位数的位置 i，判断以 i 为中位数能否选出aid总和不超过F的子序列 t。
3. 枚举的区间长度为O(C-N*2)=O(C), 每个枚举位置的判断若为O(C)一定超时。好在只是求中位数的值，不必找出所有解，甚至不必维护解，那么可以用贪心策略构造一个aid总和尽可能小的解，若其值满足条件，则说明必然有解。
4. 如何得到贪心策略的值呢，接下来的做法是参考了网上别人的思路：
预处理出两个数组before[i], after[i]，分别记录位置 i 前、后按贪心策略选出的N/2个元素所能得到的最小aid总和。
具体先对 s 序列从左到右扫描，用容量上限为N/2的大顶堆维护当前扫描位置 i 之前的aid值最小的N/2个元素，并把堆中元素值总和记录在数组元素before[i]中。
然后再进行一遍从右到左的扫描，填充数组after[i]。
这里为了减少预处理的的时间，我只对before数组进行了预处理，after数组可以随着枚举位置的移动而计算，这样一旦枚举到一个可行位置，则不必计算剩余的after[i]。
这个堆开始写搓了。。。上滤下滤忘加else break了一直T，对基本原理的掌握还是不够熟练啊
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 const int MAX_C = 100005; 6 7 int heap[MAX_C]; 8 9 void swap(int& a, int& b){ 10 int tmp = a; 11 a = b; 12 b = tmp; 13 } 14 15 struct Heap 16 { 17 int heap[MAX_C];//大顶堆 18 int size; 19 Heap(){size=0;} 20 void insert(int x){ 21 size++; 22 heap[size-1] = x; 23 int i = size - 1; 24 while(i > 0){ 25 int p = (i-1)/2; 26 if(heap[p] < heap[i]){ 27 swap(heap[p], heap[i]); 28 i = p; 29 }else break; 30 } 31 } 32 int getTop(){ 33 return heap[0]; 34 } 35 void deleteTop(){ 36 heap[0] = heap[size-1]; 37 size--; 38 int i = 0; 39 while(i*2+1 < size){ 40 int lc = i*2+1, rc=i*2+2; 41 int c = lc; 42 if(rc<size && heap[rc]>heap[lc]) 43 c = rc; 44 if(heap[c] > heap[i]){ 45 swap(heap[c], heap[i]); 46 i = c; 47 }else break; 48 } 49 } 50 }; 51 52 struct Calf 53 { 54 int score, aid; 55 }calves[MAX_C]; 56 bool cmp(Calf c1, Calf c2){ 57 return c1.score < c2.score; 58 } 59 60 int N, C, F; 61 int before[MAX_C], after[MAX_C]; 62 63 int main() 64 { 65 freopen("2010.txt", "r", stdin); 66 scanf("%d%d%d", &N, &C, &F); 67 for(int i=0; i<C; i++){ 68 scanf("%d%d", &calves[i].score, &calves[i].aid); 69 } 70 int begin = N/2; 71 int end = C-N/2-1; 72 sort(calves, calves+C, cmp); 73 74 if(N==1){ 75 printf("%d\n", calves[C-1].score); 76 return 0; 77 } 78 79 Heap hb; 80 81 //前begin的before[i]=0 82 memset(before, 0, sizeof(before)); 83 memset(after, 0, sizeof(after)); 84 85 //printf("begin=%d\nend=%d\n", begin, end); 86 for(int i=0; i<begin; i++){ //N为奇数,begin为中间数 87 hb.insert(calves[i].aid); 88 before[begin] += calves[i].aid;//前begin个必然算入before[begin] 89 } 90 //第begin个开始有对换 91 for(int i=begin+1; i<=end; i++){ 92 if(calves[i-1].aid < hb.getTop()){//有比堆顶更小的aid,对换 93 before[i] = before[i-1] - hb.getTop() + calves[i-1].aid; 94 hb.deleteTop(); 95 hb.insert(calves[i-1].aid); 96 }else before[i] = before[i-1]; 97 } 98 99 Heap ha; 100 for(int i=C-1; i>end; i--){ 101 ha.insert(calves[i].aid); 102 after[end] += calves[i].aid;//后begin个必然算入after[C-begin] 103 } 104 //printf("after[%d] = %d\n", end, after[end]); 105 int flag = -1; 106 int sum = calves[end].aid + before[end] + after[end]; 107 if(sum <= F){ 108 printf("%d\n", calves[end].score); 109 return 0; 110 } 111 for(int i=end-1; i>=begin; i--){ //开始从后往前枚举中位数i 112 if(calves[i+1].aid < ha.getTop()){ 113 after[i] = after[i+1] - ha.getTop() + calves[i+1].aid; 114 ha.deleteTop(); 115 ha.insert(calves[i+1].aid); 116 }else after[i] = after[i+1]; 117 //printf("after %d: %d\n", i, after[i]); 118 int sum = before[i] + after[i] + calves[i].aid; 119 //printf("sum %d: %d\n", i, sum); 120 if(sum <= F){ 121 flag = calves[i].score; 122 break; 123 } 124 } 125 printf("%d\n", flag); 126 return 0; 127 }
