PKU 1230 Pass-Muraille
http://poj.org/problem?id=1230
あるマジシャンが図のような壁のある空間を上から下まで一直線に移動する。
このとき、間に壁がk個より多くあると、渡り切ることが出来ない。
どの列からスタートしても上から下まで渡りきれるようにいくつか壁を取り除きたい。
取り除く必要がある壁の最小の数を答えろというような問題。
y座標は考えなくてもよく、左側座標の小さい壁から考えていって、もしk枚より多くの壁が出来たときは、重なっているもののうち、右側座標が大きい壁を取り除いていけばいい。
座標が二次元になっていて、いろいろと考えさせられました。y座標が無関係な値であるということにすぐきづけるようになりたいです。
壁の情報をリストに格納して毎回ソートしているのですが、もう少しいいやり方があるようなきがします。
PI in[100]; main(){ int t; cin>>t; while(t--){ int n,k; cin>>n>>k; rep(i,n){ int tt; int xs,xe; cin>>xs>>tt; cin>>xe>>tt; in[i].F=min(xs,xe); in[i].S=max(xs,xe); in[i].S=-in[i].S; } sort(in,in+n); list<int>q; int ans=0; rep(i,n){ q.pb(-in[i].S); q.sort(); while(!q.empty() && *q.begin()<in[i].F)q.pop_front(); while(SZ(q)>k){ ++ans; q.pop_back(); } } cout<<ans<<endl; } }