AtCoderBegginnerContest #005 C: おいしいたこ焼きの売り方
問題
Aの発生と消失の中でBが可能か判定するタイプのシミュレート問題(参考: AOJ0231 Dangerous Bridge)
解法
pair
#include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; typedef pair<int,int> Pii; int main() { vector<Pii> timeline; int T; cin >> T; int N; cin >> N; for(int i=0; i<N; i++) { int a; cin >> a; timeline.push_back(Pii(a, 1)); timeline.push_back(Pii(a+T, 3)); } int M; cin >> M; for(int j=0; j<M; j++) { int b; cin >> b; timeline.push_back(Pii(b, 2)); } sort(timeline.begin(), timeline.end()); queue<int> Q; for(int i=0; i<timeline.size(); i++) { if(timeline[i].second == 1) { Q.push(timeline[i].first); } if(timeline[i].second == 2) { if(Q.empty()) { cout << "no" << endl; return 0; } Q.pop(); } if(timeline[i].second == 3) { if(!Q.empty() && Q.front() + T == timeline[i].first) { Q.pop(); } } } cout << "yes" << endl; return 0; }