algorithm - Finding an arrangement that yield minimum salary -

once again stuck sopj problem pilots

the problem statement is..

charlie acquired airline transport company , stay in business needs lower expenses means possible. there n pilots working company (n even) , n/2 plane crews needs made. plane crew consists of 2 pilots - captain , assistant. captain must older assistant. each pilot has contract granting him 2 possible salaries - 1 captain , other assistant. captain's salary larger assistant's same pilot. however, possible assistant has larger salary captain. write program compute minimal amount of money charlie needs give pilots' salaries if decides spend time make optimal (i.e. cheapest) arrangement of pilots in crews.

input

the first line of input contains integer n, 2 ≤ n ≤ 10,000, n even, number of pilots working charlie's company. next n lines of input contain pilots' salaries. lines sorted pilot's age, salaries of youngest pilot given first. each of n lines contains 2 integers separated space character, x y, 1 ≤ y < x ≤ 100,000, salary captain (x) , salary assistant (y).

output

the first , line of output should contain minimal amount of money charlie needs give pilots' salaries.

sample

input

4  5000 3000  6000 2000  8000 1000  9000 6000  

output 19000

input

6  10000 7000  9000 3000  6000 4000  5000 1000  9000 3000  8000 6000  

output 32000

now using greedy approch clear first pilot should assistant , after check if possible save money making pilot captain if yes make him captain else assistant.

it working of cases wrong awnser.

my code is..

#define pb push_back #define mp make_pair #define fi first #define se second #define for(i,n) for(int i=0;i<n;i++)  int main() {     int n;     //freopen("input.txt","r",stdin);     cin>>n;     vector<pair<pii,int> > data;     for(i,n)     {         int csal,asal;         cin>>csal>>asal;         int diff=csal-asal;         data.pb(mp(mp(csal,asal),diff));     }     int ccount=0,acount=0,sal=0;     for(i,n)     {         if(acount<n/2)         {             int flag=1;             for(int j=i+1;j<=i+(acount-ccount);j++)             {                 if(data[i].se<=data[j].se)                 {                     //cout<<j<<" ";                     flag=0;                     break;                 }             }             if(flag)             {                 sal+=data[i].fi.se;                 acount++;             }             else             {                 sal+=data[i].fi.fi;                 ccount++;             }         }         else         {             sal+=data[i].fi.fi;                 ccount++;         }         //cout<<sal<<" "<<i<<"\n";     }     cout<<sal<<"\n";     return 0; } 

please me solve problem..

here solution o(n log n) running time. uses greedy algorithm, different yours.

1)let's assume delta[i] = x[i] - y[i].
2)now let's process pilots sorted delta[i] in descending order. assume pilots given captain positions.
3)each pilot should reassigned assistant position if possible.
that's it. claim algorithm gives correct result.

proof:
1)when pilot cannot given assistant job?
i)when there no "free" captains right(in terms of age) of him(that is, if number of captains right of him greater or equal number of assistants). why happen? if there "too many" assistants right of him. let's assume decided fix it. require changing 1 of assistants captain. if pilot assistant, processed before current pilot. means delta greater(recall iterate on them in sorted order). 1 more observation: 1 assistant can block 1 captain(because crew includes 1 captain). these 2 observation show changing when not possible make current pilot assistant make answer worse.
ii)when taken captain assistant left(in terms of age) him. fix it, necessary make guy captain again, in i). make answer worse(the proof same in situation above).
2)using mathematical induction , 2 observations above, can proven rigorously algorithm correct.
3)this algorithm produce n / 2 assistants because makes pilot assistant whenever possible , there n / 2 possibilities it.

the question remaining is: how check if possible make current pilot assistant?
here fast way: let's assign each pilot 1 if captain , -1 otherwise. let's take @ array of -1 , 1 in order of pilots' ages. claim if there suffix negative sum, configuration invalid. otherwise, valid(this statement not hard prove, not post proof here or there proofs in answer). need maintain 2 operations: change -1 1(and vice versa) , tell if there suffix negative sum. standard problem , can solved segment tree(you can store total sum , minimum suffix sum in each node, update easy because value of 1 element changed @ time(that is, value in leaf)).

the complexity o(n log n) because need sort array , during iteration @ 3 queries segment tree done per 1 step(and each query takes o(log n) time).