POJ.2010 Moo University - Financial Aid

1.Problem
http://poj.org/problem?id=2010

2.Idea
Preprocessing with priority_queue, and check every possible median values.

3.Source

 struct Cow {  
      int csat;  
      ll faid;  
      bool operator < (const Cow &a)const {  
           //if(csat == a.csat) return faid > a.faid; else   
           return csat < a.csat;  
      }  
 } Cows[100005];  
 ll d[100005], u[100005];  
 int c, n, k;  
 ll f;  
 void preProc(ll *l)  
 {  
      ll sum = 0LL;  
      priority_queue<int> q;  
      for (int i = 0; i < c; i++) {  
           if (i < k) {  
                l[i] = 13131313131313131;  
                q.push(Cows[i].faid);  
                sum += Cows[i].faid;  
           }  
           else {  
                l[i] = sum;  
                if (q.top() > Cows[i].faid) {  
                     sum += (Cows[i].faid - q.top());  
                     q.pop();   
                     q.push(Cows[i].faid);  
                }  
           }  
      }  
 }  
 int main()  
 {  
      cin >> n >> c >> f;  
      for (int i = 0; i < c; i++) {  
           cin >> Cows[i].csat >> Cows[i].faid;  
      }  
      k = n / 2;  
      sort(Cows, Cows + c);  
      preProc(d);  
      reverse(Cows, Cows + c);  
      preProc(u);  
      reverse(u, u + c);  
      reverse(Cows, Cows + c);  
      int ans = -1;  
      for (int i = 0; i < c; i++) {  
           if (d[i] + u[i] + Cows[i].faid <= f) {  
                ans = Cows[i].csat;  
           }  
      }  
      cout << ans << endl;  
      return 0;  
 }