欲張りアルゴリズムProblem C 1002田忌競馬

Problem C  Problem ID:1002 
田忌は斉王競馬と同じ数の馬を持っているが、馬ごとに出場し、一度だけ出場し、負けた人は勝った人に200両の銀を与えた.二人のすべての馬の速度を与えて、田忌が得ることができる最も多い銀を求めます.
 
問題を解く構想の形成過程:1.田忌の最も遅い馬が斉王の最も遅い馬より遅い時、田忌のこの馬と斉王の最も速い馬を比べてみる(200両負け).
 2.田忌の最も遅い馬が斉王の最も遅い馬より速い時、この2匹の馬を比べてみる(200両勝った).
 3.(ポイント)田忌が最も遅い馬と斉王が最も遅い馬の速度を同時にして、さらに2つの状況に分けて考えます.
①若田忌の最速馬は斉王の最速馬より遅いか速度が同じで、田忌の最速馬と斉王の最速馬を比べてみる.この時は負けるが、田忌が最も速い馬は将来の試合に勝つ可能性が高く、後の田忌はこの時斉王が最も遅い馬に勝つ可能性が高いため、収益が最も大きい.(注意:田忌の最も遅い馬は斉王の最も速い馬より遅いとは限らない!例えばテストサンプル:2 20 20 20 20 20)
②若田忌最速の馬が斉王最速の馬より速い場合は、まずこの2頭の最速の馬を比べて200両を獲得し、3歩目(3.)の循環判断に入る.
 
感想:大局を顧みて、どのようにして最大の収益を得ることができるかをよく分析して、一時の引き分けは甚だしきに至っては敗局は全体の収益をもっと高くすることができるかもしれません.
 
コード:

#include<iostream>
#include<stdio.h>
#include<set>
using namespace std;
int main()
{
    int n;
    multiset <int> s1,s2;
    multiset <int>::iterator s1i,s2i,s1ii,s2ii;
    while(scanf("%d",&n)!=EOF&&n){
        int n1=n,n2=n,n3=n;
        int total=0;
        while(n1--){
            int temp;
            cin>>temp;
            s1.insert(temp);
        }
        while(n2--){
            int temp;
            cin>>temp;
            s2.insert(temp);             //insert               。
        }
        s1i=s1.begin();
        s2i=s2.begin();
        for(int i=0;i<n3;++i,s1i=s1.begin(),s2i=s2.begin())
        {
            if((*s1i)<(*s2i)){           //                ，                  。
                total-=200;
                s1.erase(s1i);
                s2i=s2.end();
                s2.erase(--s2i);
            }
            else if((*s1i)>(*s2i)){     //                ，         。
                total+=200;
                s1.erase(s1i);
                s2.erase(s2i);
            }
            else if((*s1i)==(*s2i)){    //                   ，           ：
                s1ii=s1.end();
                --s1ii;
                s2ii=s2.end();
                --s2ii;
                if((*s1ii)>(*s2ii)){    //                ，             。
                    total+=200;
                    s1.erase(s1ii);
                    s2.erase(s2ii);
                }
                else{                   //                      ，                  。
                    if((*s1i)<(*s2ii))
                        total-=200;
                    s1.erase(s1i);
                    s2i=s2.end();
                    s2.erase(--s2i);    //  /            ：  end()      。
                }
            }
        }
        cout<<total<<endl;
        s1.clear();
        s2.clear();
    }
    return 0;
}