UVa : 11804 - Argentina

問題概要

http://uva.onlinejudge.org/external/118/11804.html
10人の選手の内, 5人をアタッカーに, 残り5人をディフェンダーに選ぶプログラムを作る問題.
各選手には, 名前がついていて, アタック能力とディフェンス能力がある.
ただし, 次の条件を満たすように選手を選ぶ必要がある.

• アタッカーにする選手5人のアタック能力の合計は, 最大にする必要がある
• そのような選び方が複数通りある場合, ディフェンスにする選手5人のディフェンス能力の合計を最大にする
• それでも選び方が複数通りある場合, 辞書式順で早い順に選ぶ

アルゴリズム

• アタック能力の降順
• ディフェンス能力の昇順
• 辞書式順で昇順

となるようにソートすれば, 前から5人はアタック, 6人目以降はディフェンスと分けることができる.

プログラム

class P{
public:
  string name; //なまえ
  int a,d; //アタック能力,ディフェンス能力

  P(){}
  bool operator<(const P &p)const{
    if(a == p.a){
      if(d == p.d) return name < p.name;
      return d < p.d;
    }
    return a > p.a;
  }
};

void disp(P *p){
  string name[5];
  rep(i,5) name[i] = p[i].name;
  sort(name,name+5);
  cout<<"(";
  rep(i,5){
    if(i != 0) cout<<", ";
    cout<<name[i];
  }
  cout<<")\n";
}

int main(){
  int T;
  cin>>T;

  REP(SET,1,T+1){
    cout<<"Case "<<SET<<":\n";
    P p[10];
    rep(i,10) cin>>p[i].name>>p[i].a>>p[i].d;
    sort(p,p+10);

    disp(p);
    disp(p+5);
  }
}