题意：给你c头牛，并给出每头牛的分数和花费，要求你找出其中n（n为奇数）头牛，并使这n头牛的分数的中位数尽可能大，同时这n头牛的总花费不能超过f，否则输出-1.

 

思路：首先对n头牛按分数进行排序，然后假设当前这头牛X的分数为中位数，然后求出X前面n/2头牛的最小花费和，以及后面n/2头牛的最小花费和。

　　　因为按分数排序，X的前n/2和后n/2的牛的分数肯定分别大于等于X和小于等于X，所以X的分数肯定会是中位数。

　　　所以，我们令left[i]为牛i的前n/2头牛的最小花费和，right[i]为牛i的后n/2头牛的最小花费和，然后i从c-1到0遍历，求出第一个头牛的left[i]+right[i]+X的花费 ≤ f，该头牛的分数就是所求出的最大中位数。

 

AC代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAX_N = 100005;int n,c,f, left[MAX_N], right[MAX_N], half,total,result;pair
        
          w[MAX_N];void solve(){	half = n/2;	total = 0;		priority_queue
         
           q;	for(int i = 0; i < c; i++)	{		left[i] = q.size() == half ? total : 0x3f3f3f3f;		q.push(w[i].second);		total += w[i].second;				if(q.size() > half)		{			total -= q.top();			q.pop();		}	}		total = 0;	while(!q.empty()) q.pop();	for(int i = c-1; i >= 0; i--)	{		right[i] = q.size() == half ? total : 0x3f3f3f3f;		q.push(w[i].second);		total += w[i].second;		if(q.size() > half)		{			total -= q.top();			q.pop();		}	}		result = -1;	for(int i = c-1; i >= 0; i--)	{		int x = left[i] + w[i].second + right[i];		if(x <= f)		{			result = w[i].first;			break;		}	}	printf("%d\n", result);}int main(){	scanf("%d %d %d", &n, &c, &f);	for(int i = 0; i < c; i++)		scanf("%d %d", &w[i].first, &w[i].second);	sort(w,w+c);	solve();	return 0;}