ABC006D トランプ挿入ソート

問題

D - トランプ挿入ソート

数字のかかれたＮ枚のカードから１枚を抜き取り好きな場所に挿入するという操作を何回くりかえすと昇順にソートできますか、という問題です。

考察

いろいろ考えましたが思いつきませんでした。
最長の増加部分列がわかればその長さを全体の長さから引いてやればよい、というところまでは思い至りました。

ＬＩＳという有名問題だそうです。

実装

もっとも小さな要素で構成される最長増加部分列を更新していきます。
更新場所を二分探索で求めることでＯ（ＮlogN）で解けました。

二分探索のところだけ抜き出すとこんな感じ。
イテレーターの使い方、まだ慣れてません。

lower_bound

指定された要素以上の値が現れる最初の位置のイテレータを取得する。

  for(int i=0;i<n;i++){
    auto itr=lower_bound(dp.begin(),dp.end(),a[i]);
    *itr=a[i];
  }

ACしたコード

#include <bits/stdc++.h>
using namespace std;
static const int INF=10e5;

int main(){
  int n;
  cin>>n;
  int a[n];
  vector<int>dp(n,INF);
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  for(int i=0;i<n;i++){
    auto itr=lower_bound(dp.begin(),dp.end(),a[i]);
    *itr=a[i];
  }
  for(int i=0;i<n;i++){
    //cout<<dp[i]<<endl;
    if(dp[i] == INF){
      cout<<n-i<<endl;
      return 0;
    }
  }
  cout<<0<<endl;
  return 0;
}