AtCoder Beginner Contest 241(Sponsored by Panasonic)B - Pasta
問題の要約
N本の麵からなるパスタがあり、i本目の麺の長さはAi。
これからM日間の食事計画を立てており、i日目にはパスタの麺のうち長さがちょうどBiであるようなものを1本選び、食べる。
もし、1日目からM日目の間に1日でもそのような麵が無い日があれば、食事計画は失敗となる。
また、同じ麺を複数の日に食べることはできない。
食事計画を最後まで実行することは可能か?
制約
1<=M<=N<=1000
1<=Ai<=10^9
1<=Bi<=10^9
入力
N M
A1 A2 ... AN
B1 B2 ... BM
考え方
1、Biの長さの麺がない日が1日でもあれば食事計画が失敗となる。
2、よって、麺の長さと本数を管理すればよい。
3、今回はmap<long long,int> mpを使ってみる。
4、Aiの長さをキーにして、本数を管理する。
5、Biの長さの麺が0本ならば食事計画は失敗、そうでなければBiの長さの麺をデクリメントする。
6、最後まで食事計画が実行できたならば成功。
実際のプログラム
#include<iostream>
#include<map>
using namespace std;
int main(){
int N,M;
cin >> N >> M;
map<long long,int> mp;
for(int i = 0; i < N; i++){
long long A;
cin >> A;
mp[A]++;
}
bool flag = true;
for(int i = 0; i < M; i++){
long long B;
cin >> B;
if(mp[B] == 0){
flag = false;
break;
}else{
mp[B]--;
}
}
if(flag){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
return 0;
}