題目大意：
對以下數(shù)組：
struct Cow
{
int score;
int aid;
}cows[C];
共C個cow，選出N個(N為奇數(shù))，使其aid的和在不大于給定的數(shù)F下，使這N個數(shù)的score的中位數(shù)最大。
題解：依然使用堆，我們首先對牛的score進(jìn)行排序，然后我們從第N/2頭牛開始，到第C-N/2頭牛結(jié)束。
每次假設(shè)第i頭牛就是中位數(shù)的牛，所以我們只需要計算這頭牛的前N/2和后N/2的aid部分的最小值側(cè)可。
我們知道，在一個大數(shù)據(jù)中取固定數(shù)目最大或最小數(shù)，用堆是最合理的。
最大堆：選取數(shù)據(jù)中最小的數(shù)集合。
最小堆：選取數(shù)據(jù)中最大的數(shù)的集合。
我們使用兩個數(shù)組：
before[i] : 表示第i頭牛前面的，選擇N/2頭牛，使其aid和最小的和的結(jié)果。
當(dāng)i < N/2時，為0
after[i] : 表示第i頭牛后面的，選擇N/2頭牛，使其aid和最小的和的結(jié)果。
當(dāng)i >= C - N/2時，為0
最后倒敘求，當(dāng)符合條件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 閱讀(2498)
評論(1) 編輯 收藏 引用 所屬分類:
算法題解