题目大意:
对以下数组:
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 阅读(2473)
评论(1) 编辑 收藏 引用 所属分类:
算法题解