| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
使用三个堆进行排序的 140K内存 0MS 代码 ,这道题的重点是贪心处理时的逻辑#include <iostream> using namespace std; struct Cow { int minimum_SPF; int maximum_SPF; }minimum_SPF_greater_priority_queue[2502], maximum_SPF_greater_priority_queue[2502]; struct Milk { int SPF; int cover_amount; }SPF_greater_priority_queue[2502]; int heap1_size = 0, heap2_size = 0, heap3_size = 0; //使用三个堆进行排序 void heap1_push(Cow a); void heap1_pop(); void heap2_push(Cow b); void heap2_pop(); void heap3_push(Milk c); void heap3_pop(); int main() { Cow intermediate_Cow; Milk intermediate_Milk; int C, L; int answer = 0; scanf_s("%d%d", &C, &L); for (int i = 0; i < C; i++) { scanf_s("%d%d", &intermediate_Cow.minimum_SPF, &intermediate_Cow.maximum_SPF); heap1_push(intermediate_Cow); } for (int i = 0; i < L; i++) { scanf_s("%d%d", &intermediate_Milk.SPF, &intermediate_Milk.cover_amount); heap3_push(intermediate_Milk); } while (heap3_size)//重点是这个循环的逻辑 { while ((minimum_SPF_greater_priority_queue[0].minimum_SPF <= SPF_greater_priority_queue[0].SPF) && heap1_size) { heap2_push(minimum_SPF_greater_priority_queue[0]); heap1_pop(); } while (heap2_size&&SPF_greater_priority_queue[0].cover_amount) { intermediate_Cow = maximum_SPF_greater_priority_queue[0]; heap2_pop(); if (SPF_greater_priority_queue[0].cover_amount && (intermediate_Cow.maximum_SPF >= SPF_greater_priority_queue[0].SPF)) { answer++; SPF_greater_priority_queue[0].cover_amount--; } } heap3_pop(); } printf_s("%d\n", answer); return 0; } //下边是三个排序堆的实现 void heap1_push(Cow a) { static Cow intermediate_Cow; int me = heap1_size; heap1_size++; int father; minimum_SPF_greater_priority_queue[me] = a; while (me) { father = (me - 1) / 2; if (minimum_SPF_greater_priority_queue[father].minimum_SPF > minimum_SPF_greater_priority_queue[me].minimum_SPF) { intermediate_Cow = minimum_SPF_greater_priority_queue[father]; minimum_SPF_greater_priority_queue[father] = minimum_SPF_greater_priority_queue[me]; minimum_SPF_greater_priority_queue[me] = intermediate_Cow; } else { break; } me = father; } return; } void heap1_pop() { static Cow intermediate_Cow; int son; int me = 0; heap1_size--; minimum_SPF_greater_priority_queue[0] = minimum_SPF_greater_priority_queue[heap1_size]; while (2 * me < heap1_size) { son = 2 * me + 1; if (minimum_SPF_greater_priority_queue[son].minimum_SPF > minimum_SPF_greater_priority_queue[son + 1].minimum_SPF&&son < heap1_size) { son++; } if (minimum_SPF_greater_priority_queue[son].minimum_SPF < minimum_SPF_greater_priority_queue[me].minimum_SPF) { intermediate_Cow = minimum_SPF_greater_priority_queue[son]; minimum_SPF_greater_priority_queue[son] = minimum_SPF_greater_priority_queue[me]; minimum_SPF_greater_priority_queue[me] = intermediate_Cow; } else { break; } me = son; } return; } void heap2_push(Cow b) { static Cow intermediate_Cow; int me = heap2_size; heap2_size++; int father; maximum_SPF_greater_priority_queue[me] = b; while (me) { father = (me - 1) / 2; if (maximum_SPF_greater_priority_queue[father].maximum_SPF > maximum_SPF_greater_priority_queue[me].maximum_SPF) { intermediate_Cow = maximum_SPF_greater_priority_queue[father]; maximum_SPF_greater_priority_queue[father] = maximum_SPF_greater_priority_queue[me]; maximum_SPF_greater_priority_queue[me] = intermediate_Cow; } else { break; } me = father; } return; } void heap2_pop() { static Cow intermediate_Cow; int son; int me = 0; heap2_size--; maximum_SPF_greater_priority_queue[0] = maximum_SPF_greater_priority_queue[heap2_size]; while (2 * me < heap2_size) { son = 2 * me + 1; if (maximum_SPF_greater_priority_queue[son].maximum_SPF > maximum_SPF_greater_priority_queue[son + 1].maximum_SPF&&son < heap2_size) { son++; } if (maximum_SPF_greater_priority_queue[son].maximum_SPF < maximum_SPF_greater_priority_queue[me].maximum_SPF) { intermediate_Cow = maximum_SPF_greater_priority_queue[son]; maximum_SPF_greater_priority_queue[son] = maximum_SPF_greater_priority_queue[me]; maximum_SPF_greater_priority_queue[me] = intermediate_Cow; } else { break; } me = son; } return; } void heap3_push(Milk c) { static Milk intermediate_Milk; int me = heap3_size; heap3_size++; int father; SPF_greater_priority_queue[me] = c; while (me) { father = (me - 1) / 2; if (SPF_greater_priority_queue[father].SPF > SPF_greater_priority_queue[me].SPF) { intermediate_Milk = SPF_greater_priority_queue[father]; SPF_greater_priority_queue[father] = SPF_greater_priority_queue[me]; SPF_greater_priority_queue[me] = intermediate_Milk; } else { break; } me = father; } return; } void heap3_pop() { static Milk intermediate_Milk; int son; int me = 0; heap3_size--; SPF_greater_priority_queue[0] = SPF_greater_priority_queue[heap3_size]; while (2 * me < heap3_size) { son = 2 * me + 1; if (SPF_greater_priority_queue[son].SPF > SPF_greater_priority_queue[son + 1].SPF) { son++; } if (SPF_greater_priority_queue[son].SPF < SPF_greater_priority_queue[me].SPF&&son < heap3_size) { intermediate_Milk = SPF_greater_priority_queue[son]; SPF_greater_priority_queue[son] = SPF_greater_priority_queue[me]; SPF_greater_priority_queue[me] = intermediate_Milk; } else { break; } me = son; } return; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator