先将所有的野怪按照价值由高到低排序，假设 $k$ 是打野怪中排名中间的那只，按照排序可知，$[1,k-1]$ 中的野怪必定被打掉了 $\frac{n-1}2$ 只，$[k+1,c]$ 中也必定被打掉了 $\frac{n-1}2$ 只，而且无论打掉的是谁，分数是怎么样，最后影响答案的都只是 $k$ 的分数。于是，可以预处理 $dpl_i$ 代表 $[1,i]$ 只野怪中选出 $\frac{n-1}2$ 只野的最小花费，$dpr_i$代表 $[i,c]$ 只野怪中选出 $\frac{n-1}2$ 只的花费。

可以从左边和右边分别维护一个优先队列求解 $dpl$ 和 $dpr$。左边的优先队列里面有 $\frac{n-1}2$ 个元素，即位于中位数左边的最优的野怪（总花费最小），首先将第 $\frac{n+1}2$ 只之前的所有野怪入队并求出其和 $L$。然后从左边第 $\frac{n+1}2$ 只怪开始往右扫，每遇到一只，更新 $dpl$ 的值（$dpl_i=L$）如果当前野怪的花费比优先队列中花费最大的野怪小，那么需要更新优先队列和 $L$。右边同理。

之后从右遍历一次可能的野怪（因为要最大的中位数），$dpl_i+dpr_i+cost_i\leqslant f$ 的话答案就是 $val_i$ 了。dp 的时间复杂度为 $O(c\log n)$，最后遍历的时间复杂度为 $O(c)$，总时间复杂度为 $O(c\log n)$。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=101000;
int dpl[N],dpr[N];
priority_queue<int> Q;
struct Data
{
    int s,f;
}cow[N];
bool comp(Data a,Data b)
{
    if(a.s!=b.s)
        return a.s>b.s;
    else
        return a.f<b.f;
}
int main()
{
    int n,c,f;
    while(scanf("%d%d%d",&n,&c,&f)!=EOF)
    {
        int nu=(n-1)/2;
        for(int i=1;i<=c;i++)
            scanf("%d%d",&cow[i].s,&cow[i].f);
        sort(cow+1,cow+c+1,comp);
        while(!Q.empty())
            Q.pop();
        int sum=0;
        for(int i=1;i<=nu;i++)
            Q.push(cow[i].f),sum+=cow[i].f;
        dpl[nu]=sum;
        for(int i=nu+1;i<=c;i++)
        {
            if(cow[i].f>=Q.top())
                dpl[i]=sum;
            else
            {
                sum=sum-Q.top()+cow[i].f;
                Q.pop();
                Q.push(cow[i].f);
                dpl[i]=sum;
            }
        }
        sum=0;
        while(!Q.empty())
            Q.pop();
        for(int i=c;i>=c-nu+1;i--)
            Q.push(cow[i].f),sum+=cow[i].f;
        dpr[c-nu+1]=sum;
        for(int i=c-nu;i>=1;i--)
        {
            if(cow[i].f>=Q.top())
                dpr[i]=sum;
            else
            {
                sum=sum-Q.top()+cow[i].f;
                Q.pop();
                Q.push(cow[i].f);
                dpr[i]=sum;
            }
        }
        bool flag=false;
        for(int i=nu+1;i<=c-nu;i++)
        {
            if(cow[i].f+dpl[i-1]+dpr[i+1]<=f)
            {
                flag=true;
                printf("%d\n",cow[i].s);
                break;
            }
        }
        if(!flag)
            printf("-1\n");
    }
    return 0;
}