首页 > 代码库 > POJ 2010 Moo University - Financial Aid 堆的高级应用 -- 维护最小(最大和)
POJ 2010 Moo University - Financial Aid 堆的高级应用 -- 维护最小(最大和)
题目大意:有N头牛,每头牛两个权值,A和B。从这N头牛中选取C头牛,使得:
1、这些牛中A权值的中位数尽量大。
2、这些牛的B权值的和小于题中所给的F
输出这个最大的A权值的中位数;如果没有满足题意的解,就输出-1。值。
思路:
堆有一个神奇的功能。假设上图是一个数组,在B从A到C移动的过程中,利用大根堆可以维护出B在所有位置时,从A到B中选K个值的和的最小值,并在nlogn内得到答案。
方法如下:先把[A,A + K]的元素加入到一个大根堆中,记录它们的总和。之后让B不断向后循环,把B加入到大根堆中,sum += B,在把大根堆中的最大值取出,sum -= MAX。
此时的sum值就是[A,B]中选K个元素的最大和,因为堆中的元素就是[A,B]中最小的K个数,sum维护的就是堆中数的总和。
运用这种方法就可以解决这个题。
先将输入数据按照A权值有小到大排序。从左到右扫一遍数组,从右到左扫一遍数组,记录一个sum数组,sum[i]表示当牛i作为A权值的中位数时,所能取到B权值和的最小值(不包括在自己)。最后从后往前扫一遍,枚举第i头牛做A权值中位数的情况,当sum[i]加上自己的A权值小于等于F时输出答案就可以了。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1000000 using namespace std; struct Complex{ int x,y; bool operator <(const Complex &a)const { return x < a.x; } }cow[MAX]; struct BigHeap{ int num[MAX],last; int Top() { return num[1]; } void Insert(int x) { num[++last] = x; int now = last; while(num[now] > num[now >> 1] && now > 1) swap(num[now],num[now >> 1]),now >>= 1; } void Pop() { num[1] = num[last--]; int now = 2; while(now <= last) { if(num[now] < num[now + 1]) now++; if(num[now] > num[now >> 1]) swap(num[now],num[now >> 1]),now <<= 1; else break; } } void Clear() { last = 0; } }heap; int points,select,limit; int sum[MAX]; int main() { cin >> select >> points >> limit; for(int i = 1;i <= points; ++i) scanf("%d%d",&cow[i].x,&cow[i].y); sort(cow + 1,cow + points + 1); select >>= 1; int temp = 0; for(int i = 1;i <= select; ++i) { temp += cow[i].y; heap.Insert(cow[i].y); } sum[select + 1] = temp; for(int i = select + 1;i < points; ++i) { heap.Insert(cow[i].y); temp += cow[i].y; temp -= heap.Top(); heap.Pop(); sum[i + 1] = temp; } temp = 0,heap.Clear(); for(int i = points;i > points - select; --i) { temp += cow[i].y; heap.Insert(cow[i].y); } sum[points - select] += temp; for(int i = points - select;i >= select; --i) { heap.Insert(cow[i].y); temp += cow[i].y; temp -= heap.Top(); heap.Pop(); sum[i - 1] += temp; } int ans = -1; for(int i = points - select;i >= select + 1; --i) if(sum[i] + cow[i].y <= limit) { ans = cow[i].x; break; } cout << ans << endl; return 0; }
POJ 2010 Moo University - Financial Aid 堆的高级应用 -- 维护最小(最大和)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。