ABC 030 C - 飛行機乗り
問題概要
省略
解法
貪欲に選んでいけばいい。なぜなら、飛行時間はxとyで決まっているので、乗れるだけ早い時間にのり、もう一方の空港に行っているほうが得。(損はない)
実装方法だが、今どちらの空港にいるのかが判断できるものと、いまの時刻がわかればよい。あとは、それぞれの空港で、出発時刻を前から見ていき、現在の時間以上の時間のものがあれば、それにのり、相手の空港にいくようにすればいい。ひとつ注意することは、毎回a1から現在の時刻以上のaiを探そうとすると遅くなるので、どこまで見たかをi、jで記憶している。
ミス
入力を間違えていて、くそみたいにwaをはやした。
コード
#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) int n, m, x, y; int a[100010], b[100010]; int main(void){ cin >> n >> m >> x >> y; rep(i, n) cin >> a[i]; rep(i, m) cin >> b[i]; int i = 0, j = 0, now = 0; int cnt = 0; bool f = false; while(1){ if(f) break; if(cnt % 2 == 0){//a空港 for (int d = i; d < n; ++d){ if(now <= a[d]){ now = a[d] + x; cnt++; i = d; break; } if(d == n - 1){ f = true; break; } } }else{//b空港 for (int d = j; d < m; ++d){ if(now <= b[d]){ now = b[d] + y; cnt++; j = d; break; } if(d == m - 1){ f = true; break; } } } } printf("%d\n", cnt / 2); return 0; }
きれいに実装した
#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) int n, m, x, y; int a[100010], b[100010]; int main(void){ cin >> n >> m >> x >> y; rep(i, n) cin >> a[i]; rep(i, m) cin >> b[i]; int i = 0, j = 0, now = 0; int cnt = 0; while(1){ if(cnt % 2 == 0){//a空港 while(i < n && a[i] < now) i++; if(i == n) break; cnt++; now = a[i] + x; }else{//b空港 while(j < m && b[j] < now) j++; if(j == m) break; cnt++; now = b[j] + y; } } printf("%d\n", cnt / 2); return 0; }