srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

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;
}