PKU 3282 Ferry Loading IV
http://poj.org/problem?id=3282
フェリーで川の端から端まで車を運ぶ。
このとき、両端から車がくるので、フェリーの移動回数ができるだけ少なくなるように運んだ時の、横断回数を求めろというような問題
一旦川を渡ったら、詰め込めるだけ詰め込んで、逆側にいくようにする。
最初、車をのせる順番を川の左右関係なく順番どおりに舟にのせないといけないと勘違いしてはまりました。
void solve(){ ll l,m; cin >> l >> m; l *= 100; int ans=0; ll cl=0; int pos=0; queue<int> q[2]; rep(j,m){ int le; string s; cin >> le >> s; q[s=="right"].push(le); } while(!q[0].empty() || !q[1].empty()){ if(!q[pos].empty() && q[pos].front()+cl<=l){ cl += q[pos].front(); q[pos].pop(); }else if(!q[!pos].empty()){ ans += 1; cl=q[!pos].front(); q[!pos].pop(); pos=!pos; }else{ ans += 2; cl=q[pos].front(); q[pos].pop(); } } cout << 1+ans << endl; } main(){ int n; cin >> n; rep(i,n) solve(); }