poj 2287貪欲(田忌競馬)

标题:田忌競馬.馬ごとに能力値を与えて、1試合に勝って200元勝って、1試合に負けて200元負けて、引き分けのお金の数は変わらない.問収益が最も大きい.
考え方(http://blog.csdn.net/zhang20072844/article/details/8126344):貪欲な策略:1、田忌の最速馬が斉王の最速馬より速いなら、両者を比べる.(田忌の他の馬では勝てない可能性が高いので、両者を比べます)2、田忌の最速馬が斉王の最速馬より遅い場合は、田忌の最速馬と斉王の最速馬で比べます.(すべての馬が斉王の最速馬に勝てないため、損失が最も小さいものを使って、最も遅いものを彼と比べる)3、等しければ、田忌の最も遅い馬と斉王の最も遅い馬3.1を比較し、若田忌の最も遅い馬は斉王の最も遅い馬より速く、両者を比べる.△田忌の一番遅い馬は一人で勝つことができる以上、斉王の一番遅い馬も彼と比べなければならないに違いない.だから、一番小さい馬を選んで彼より速い.(どうせすべての馬は田忌の一番遅い馬より速いから、この馬は必ず負ける(この場所はまだよく分からない)、貢献が一番大きいのを選んで、斉王の一番速い馬を殺す)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 1005
int t[N],k[N];
int n;
int cmp(const void* a,const void* b){
    return (*(int*)a) - (*(int*)b);
}
int main(){
    while(scanf("%d",&n) && n){
        int res=0,i,ti,ki,tj,kj;
        for(i = 1;i<=n;i++)
            scanf("%d",&t[i]);
        for(i = 1;i<=n;i++)
            scanf("%d",&k[i]);
        qsort(t+1,n,sizeof(int),cmp);
        qsort(k+1,n,sizeof(int),cmp);
        ti = ki = 1;//t    ，k    ；ij    
        tj = kj = n;
        while(ti!=tj){
            if(t[ti] < k[ki] || t[tj] < k[kj]){
                ti++;
                kj--;
                res -= 200;
            }else if(t[tj] > k[kj]){
                tj--;
                kj--;
                res += 200;
            }else if(k[ki] < t[ti]){
                ti++;
                ki++;
                res += 200;
            }else{
                if(t[ti] < k[kj])
                    res -= 200;
                ti++;
                kj--;
            }
        }
        if(t[ti] < k[ki])
            res -= 200;
        else if(t[ti] > k[ki])
            res += 200;
        printf("%d
",res);
    }
    return 0;
}