提出AC↓
Submission #8508519 - CODE FESTIVAL 2017 qual B
int main()
{
cout <<setprecision(10);
ll n ; cin >> n;
vector<ll> D(n);
rep(i,n){
cin >> D[i];
}
SORT(D);
ll m ; cin >> m;
vector<ll> T(m);
rep(i,m) cin >> T[i];
SORT(T);
ll start = 0 ;
ll count = 0;
rep(i,m){
//難易度がT[i]となるものを探す 二分探索
ll search = T[i];
For(j,start,n){
if(D[j] == search){
//ok
start = j+1;
count ++;
break;
}
}
}
if(count==m){
cout<<"YES"<<endl;
}else cout << "NO"<<endl;
}解法
難易度がT[i]となるものを探す 二分探索 これは嘘です
二分探索で探していこうと思ったのですが、それだと同じ必要難易度があったときに、すでにそれを使ったかどうかみたいなのが分からなくなる。
vectorで要素の削除をするのは、配列変数.pop_backで 末尾を消せるらしいですけど途中は消せないので。
嘘ついた
eraseを使えば消せるらしいです
vector::erase - cpprefjp C++日本語リファレンス
計算量⇒削除される要素の数と同じ回数のTのデストラクタが実行される。
何言ってるのか分からないっすね
だから、どちらもソートして難易度の値が小さいものから探していく。
見つかったらその次の難易度のものは、その見つかったものの次の要素番号から探す。
ということで実装してみました。
二分探索を使うのであればeraseが使えるかもしれない
でもmapなり僕の解法のほうが圧倒的に楽だと思う
