Are you watching closely?
Every great magic trick consists of three acts. The first act is
called The Pledge, the magician shows you something ordinary, but of
course, it probably isn't. The second act is called The Turn. The
magician makes his ordinary something do something extraordinary. Now,
if you're looking for the secret，you won't find it. That's why there's a
third act, called The Prestige. This is the part with the twists and
turns, where lives hang in the balance, and you see something shocking
you've never seen before.
Li Lei and Han Meimei are magicians and they want to act the
prestige. So they need to divide the props for the magic show. They have
decided upon the following procedure: they choose props one by one, in
turn, until all the props are chosen.
Li Lei and Han Meimei have different strategies in deciding what to
choose. When faced with a choice, Li Lei always selects the prop that is
most valuable to him. In case of a tie, he is very considerate and
picks the one that is least valuable to Han Meimei. (Since Li Lei and
Han Meimei are good friends, they know exactly how much value the other
places on each prop.)
Han Meimei’s strategy, however, consists of maximizing her own final
value(The total value of all the props she picked). She is also very
considerate, so if multiple choices lead to the same optimal result, she
prefers Li Lei to have as much final value as possible.
You are given the result that who chooses first. After Li Lei and Han
Meimei have finished dividing all the props between themselves, what is
the total value of the props each of them ends up with?
On the first line a positive integer: the number of test cases, at most 100. After that per test case:
n(1≤n≤1,000): the number of props.n lines with two integers li and hi (0≤li, hi≤1000)
For each test case, output one line with two integers: the
value Li Lei gets and the value Han Meimei gets. Both values must be
according to their own valuations.
#include <stdio.h>
void sort(int data1[], int data2[], int order[], int n){
int i,j, tmp;
int o1, o2;
for(i=0; i<n; i++){
for(j=n-1; j>i; j--){
o1 = order[j];
o2 = order[j-1];
if( ( data1[o1] > data1[o2] )
|| (data1[o1] == data1[o2] && data2[o1] < data2[o2]) ){
//swap j and j-1
order[j] = o2;
order[j-1] = o1;
}
}
}
}
void main(){
int t,lines,i,j,k;
char c;
int propl[1000];
int proph[1000];
int orderl[1000];
int orderh[1000];
int visited[1000];
int s;
int ls;
int hs;
int suml, sumh;
int min, minOrder;
scanf(" %d", &t);
while(t--){
scanf(" %d", &lines);
scanf(" %c", &c);
s = c=='L'?0:1;
i = 0;
for(i=0; i<lines; i++){
scanf(" %d %d", &propl[i], &proph[i]);
}
for(i=0; i<lines; i++){
orderl[i] = i;
orderh[i] = i;
visited[i] = 0;
}
sort(propl, proph, orderl, lines);
sort(proph, propl, orderh, lines);
hs = lines/2;
if(s == 1){
if(lines - hs > hs){
hs += 1;
}
}
ls = -1;
suml = 0;
sumh = 0;
for(i=0; i<lines; i++){
if(s++%2){
k = hs;
j = -1;
min = 99999;
minOrder = 0;
while(k>0){
if(!visited[orderh[++j]]){
if(min > proph[ orderh[j] ]){
min = proph[ orderh[j] ];
minOrder = j;
}
k--;
}
}
hs--;
sumh += proph[ orderh[minOrder] ];
visited[orderh[minOrder]] = 1;
}else{
while(visited[ orderl[++ls] ]);
suml += propl[ orderl[ls] ];
visited[ orderl[ls] ] = 1;
}
}
printf("%d %d\n", suml, sumh);
}
}