题目大意：
对以下数组：
struct Cow
{
int score;
int aid;
}cows[C];
共C个cow，选出N个(N为奇数)，使其aid的和在不大于给定的数F下，使这N个数的score的中位数最大。
题解：依然使用堆，我们首先对牛的score进行排序，然后我们从第N/2头牛开始，到第C-N/2头牛结束。
每次假设第i头牛就是中位数的牛，所以我们只需要计算这头牛的前N/2和后N/2的aid部分的最小值侧可。
我们知道，在一个大数据中取固定数目最大或最小数，用堆是最合理的。
最大堆：选取数据中最小的数集合。
最小堆：选取数据中最大的数的集合。
我们使用两个数组：
before[i] : 表示第i头牛前面的，选择N/2头牛，使其aid和最小的和的结果。
当i < N/2时，为0
after[i] : 表示第i头牛后面的，选择N/2头牛，使其aid和最小的和的结果。
当i >= C - N/2时，为0
最后倒叙求，当符合条件after[i]+cows[i].aid + before[i] <= f就打印退出
代码：
#include <stdio.h>
#include <algorithm>
using namespace std;
const int C = 100005;
const int N = 20000;
int n,c,f;
struct Cow
{
int score;
int aid;
friend bool operator < (const Cow& _a,const Cow &_b)
{
return _a.score < _b.score;
}
};
Cow cows[C];
int before[C];
int after[C];
template<typename _Type>
class MaxHeap
{
private:
_Type data[N];
int size;
int cur;
public:
MaxHeap():size(0),cur(0){}
MaxHeap(int _n):size(_n),cur(0)
{
memset(data,0,sizeof(data));
data[0] = 1 << 30;
}
~MaxHeap()
{
}
void clear(int _n)
{
memset(data,0,sizeof(data));
cur = 0;
data[0] = 1 << 30;
size = _n;
}
void push(_Type _value)
{
if(isFull())
{
return ;
}
cur ++;
int i;
for(i = cur; data[i/2] < _value;i/=2)
{
data[i] = data[i/2];
}
data[i] = _value;
}
void pop()
{
if(isEmpty())
return ;
int lastElement = data[cur];
data[cur] = 0;
--cur;
int child = 0;
int i = 0;
for(i = 1; i*2 <= cur; i = child)
{
child = i*2;
if(child != cur && data[child+1] > data[child])
{
++child;
}
if(lastElement < data[child])
data[i] = data[child];
else
break;
}
data[i] = lastElement;
}
int front()const
{
return data[1];
}
bool isFull()const
{
return cur >= size;
}
bool isEmpty()
{
return cur == 0;
}
};
MaxHeap<int> heap;
void Test()
{
for (int i = 0; i < c; ++i)
{
scanf("%d %d",&(cows[i].score),&(cows[i].aid));
}
sort(cows,cows+c);
int heapSize = n/2;
heap.clear(heapSize);
for (int i = 0; i < heapSize; ++i)
{
heap.push(cows[i].aid);
before[heapSize] += cows[i].aid;
}
for (int i = heapSize+1; i < c - heapSize; ++i)
{
int fontV = heap.front();
if (fontV > cows[i-1].aid)
{
heap.pop();
heap.push(cows[i-1].aid);
before[i] = before[i-1] - fontV + cows[i-1].aid;
}
else
{
before[i] = before[i-1];
}
}
heap.clear(heapSize);
for (int i = c-1; i > c - 1 - heapSize; --i)
{
heap.push(cows[i].aid);
after[c-1-heapSize] += cows[i].aid;
}
for (int i = c - 2 - heapSize; i >= heapSize; --i)
{
int fontV = heap.front();
if (fontV > cows[i+1].aid)
{
heap.pop();
heap.push(cows[i+1].aid);
after[i] = after[i+1] - fontV + cows[i+1].aid;
}
else
{
after[i] = after[i+1];
}
}
for (int i = c - 1 - heapSize; i >= heapSize; --i)
{
if (after[i] + before[i] + cows[i].aid <= f)
{
printf("%d\n",cows[i].score);
return;
}
}
printf("-1\n");
}
int main()
{
//freopen("data.txt","r",stdin);
while(scanf("%d %d %d",&n,&c,&f) != EOF)
{
Test();
}
return 0;
}posted on 2011-10-19 11:04
bennycen 阅读(2468)
评论(1) 编辑 收藏 引用 所属分类:
算法题解