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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理