敗戦記

PKU 1065 Wooden Sticks

PKU

http://poj.org/problem?id=1065

棒があって、それぞれの棒を処理するための道具がある？

道具は最初のセットアップに1分かかり、もし今処理した棒の次に処理する棒の長さと重さが両方共今処理した棒以上であれば、セットアップに時間はかからない。

全体としてセットアップにかかる時間の最小値を求めろというような問題。

なんとなく考えた方法の反例が思いつかないので投げたら通ったという微妙なAC。

重さと長さをpair<int,int>に突っ込んでソートしたあとに、下から見ていってまだ処理されていなければ、それより後の棒で処理されていない、かつセットアップ0で処理できるものを可能なかぎり貪欲に処理するというようなアルゴリズムです。

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;
  }
}

Permalink | コメント(0) | トラックバック(0) | 10:08