想定解フローなの…?
http://yukicoder.me/problems/297
問題
A君はA枚のカードを持ち、それぞれの強さはB[i]である。
C君はC枚のカードを持ち、それぞれの強さはD[i]である。
2人はN回試合を行う。
試合では両者手持ちのカードを1枚場にだし、その強さを競う。
当然強いカードの方が勝つ。
場に出したカードは以後使えない。
ただし手持ちのカードがなくなると、自分のカードを回収して再度すべて使うことができるようになる。
C君がA君の望むカードを出してくれる場合、A君は最大何回勝利できるか。
解法
想定解はフローらしいが…。
自分は別解法で解いた。
基本アプローチは、A君が勝てるならギリギリ勝てる組み合わせ、どうせ勝てないならA君は弱いカード、C君は強いカードを消費するようにすればよい。
具体的には、以下の処理を試合毎に繰り返せばよい。
- A君が勝てる場合、A君は勝てるうち最弱のカードをだし、C君はそれに負ける最強のカードを消費する。
- どうカードを出しても勝てない場合、A君は最弱、C君は最強のカードを消費する。
int N,A,C; vector<int> BB,DD,B,D; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>A; FOR(i,A) cin>>x, BB.push_back(x); cin>>C; FOR(i,C) cin>>x, DD.push_back(x); int ret=0; while(N--) { if(B.empty()) B=BB; if(D.empty()) D=DD; sort(B.begin(),B.end()); sort(D.begin(),D.end()); int win=0; FOR(x,B.size()) { for(y=D.size()-1;y>=0;y--) if(B[x]>D[y]) { ret++; win=1; B.erase(B.begin()+x); D.erase(D.begin()+y); break; } if(win) break; } if(!win) { B.erase(B.begin()); D.erase(D.begin()+D.size()-1); } } cout<<ret<<endl; }
まとめ
フローを思いつけと言われると★4だけど、貪欲で通るので★3でもいいかなぁ。
N,A,Cが大きいと分からないけどね。