题目大意:
对以下数组:
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;
![](/Images/OutliningIndicators/None.gif)
const int C = 100005;
const int N = 20000;
int n,c,f;
![](/Images/OutliningIndicators/None.gif)
struct Cow
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
int score;
int aid;
friend bool operator < (const Cow& _a,const Cow &_b)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return _a.score < _b.score;
}
};
Cow cows[C];
![](/Images/OutliningIndicators/None.gif)
int before[C];
int after[C];
![](/Images/OutliningIndicators/None.gif)
template<typename _Type>
class MaxHeap
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
private:
_Type data[N];
int size;
int cur;
public:
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
MaxHeap():size(0),cur(0)
{}
MaxHeap(int _n):size(_n),cur(0)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
memset(data,0,sizeof(data));
data[0] = 1 << 30;
}
~MaxHeap()
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
![](/Images/OutliningIndicators/InBlock.gif)
}
void clear(int _n)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
memset(data,0,sizeof(data));
cur = 0;
data[0] = 1 << 30;
size = _n;
}
![](/Images/OutliningIndicators/InBlock.gif)
void push(_Type _value)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(isFull())
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return ;
}
cur ++;
int i;
for(i = cur; data[i/2] < _value;i/=2)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
data[i] = data[i/2];
}
data[i] = _value;
}
![](/Images/OutliningIndicators/InBlock.gif)
void pop()
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
child = i*2;
if(child != cur && data[child+1] > data[child])
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
++child;
}
if(lastElement < data[child])
data[i] = data[child];
else
break;
}
data[i] = lastElement;
}
![](/Images/OutliningIndicators/InBlock.gif)
int front()const
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return data[1];
}
![](/Images/OutliningIndicators/InBlock.gif)
bool isFull()const
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return cur >= size;
}
bool isEmpty()
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return cur == 0;
}
};
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
MaxHeap<int> heap;
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
void Test()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
for (int i = 0; i < c; ++i)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
heap.push(cows[i].aid);
before[heapSize] += cows[i].aid;
}
for (int i = heapSize+1; i < c - heapSize; ++i)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int fontV = heap.front();
if (fontV > cows[i-1].aid)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
heap.pop();
heap.push(cows[i-1].aid);
before[i] = before[i-1] - fontV + cows[i-1].aid;
}
else
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
before[i] = before[i-1];
}
}
![](/Images/OutliningIndicators/InBlock.gif)
heap.clear(heapSize);
for (int i = c-1; i > c - 1 - heapSize; --i)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
heap.push(cows[i].aid);
after[c-1-heapSize] += cows[i].aid;
}
for (int i = c - 2 - heapSize; i >= heapSize; --i)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int fontV = heap.front();
if (fontV > cows[i+1].aid)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
heap.pop();
heap.push(cows[i+1].aid);
after[i] = after[i+1] - fontV + cows[i+1].aid;
}
else
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
after[i] = after[i+1];
}
}
![](/Images/OutliningIndicators/InBlock.gif)
for (int i = c - 1 - heapSize; i >= heapSize; --i)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if (after[i] + before[i] + cows[i].aid <= f)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf("%d\n",cows[i].score);
return;
}
}
printf("-1\n");
}
![](/Images/OutliningIndicators/None.gif)
int main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](/Images/OutliningIndicators/ContractedBlock.gif)
{
//freopen("data.txt","r",stdin);
while(scanf("%d %d %d",&n,&c,&f) != EOF)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
Test();
}
return 0;
}
posted on 2011-10-19 11:04
bennycen 阅读(2460)
评论(1) 编辑 收藏 引用 所属分类:
算法题解