PKU 1065 Wooden Sticks
http://poj.org/problem?id=1065
棒があって、それぞれの棒を処理するための道具がある?
道具は最初のセットアップに1分かかり、もし今処理した棒の次に処理する棒の長さと重さが両方共今処理した棒以上であれば、セットアップに時間はかからない。
全体としてセットアップにかかる時間の最小値を求めろというような問題。
なんとなく考えた方法の反例が思いつかないので投げたら通ったという微妙なAC。
重さと長さをpair
O(n^2)
PI in[5000]; bool use[5000]; main(){ int T; cin>>T; while(T--){ int n; cin>>n; memset(use,0,sizeof(use)); rep(i,n){ cin>>in[i].F>>in[i].S; } sort(in,in+n); int ans=0; rep(i,n){ if(use[i])continue; use[i]=true; ++ans; int ti=i; for(int j=i+1;j<n;j++){ if(use[j])continue; if(in[ti].S<=in[j].S){ use[j]=true; ti=j; } } } cout<<ans<<endl; } }