Codeforces 479D Long Jumps(貪心+二分)

Codeforces 479D Long Jumps(貪心+二分)

題目鏈接：Codeforces 479D Long Jumps

題目大意：valery是個體育老師，現在他要為學生考跳遠，女生標准為x，男生為y，現在一個長為L的刻度尺，有N個刻

度，給定N個刻度，現在為說還需要加幾個刻度才能測量x，y這兩個長度。

解題思路：因為總共就x，y兩個長度，所以最多加兩個刻度。所以只要判斷不加和加一個的情況即可。

先枚舉每個刻度a[i]，然後用二分查找一下a[i]+x或者a[i]-x刻度存不存在，同理y。如果x和y都通過判斷，那麼就是不需

要加刻度。

如果只通過x或只通過y，只需要加一個刻度。

有一種情況就為x和y都沒有通過，但是加一個刻度就夠了，這種情況，只要枚舉加刻度的位置即可。

#include 
#include 
#include 

using namespace std;

const int maxn = 1e5+5;
int N, L,  X, Y, A[maxn];

bool judge (int u) {
    if (u < 0 || u > L) return false;
    int k = lower_bound(A, A + N, u) - A;
    return u == A[k];
}

void solve () {
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (judge(A[i] - X) || judge(A[i] + X))
            ans |= 1;
        if (judge(A[i] - Y) || judge(A[i] + Y))
            ans |= 2;
    }

    if (ans == 3)
        printf("0\n");
    else if (ans == 2)
        printf("1\n%d\n", X);
    else if (ans == 1)
        printf("1\n%d\n", Y);
    else {

        for (int i = 0; i < N; i++) {
            int tx = A[i] + X;
            int ty = A[i] + Y;

            if (tx <= L && (judge(tx - Y) || judge(tx + Y))) {
                printf("1\n%d\n", tx);
                return;
            }

            if (ty <= L && (judge(ty - X) || judge(ty + X))) {
                printf("1\n%d\n", ty);
                return;
            }
        }

        for (int i = 0; i < N; i++) {
            int tx = A[i] - X;
            int ty = A[i] - Y;

            if (tx >= 0 && (judge(tx - Y) || judge(tx + Y))) {
                printf("1\n%d\n", tx);
                return;
            }

            if (ty >= 0 && (judge(ty - X) || judge(ty + X))) {
                printf("1\n%d\n", ty);
                return;
            }
        }
        printf("2\n%d %d\n", X, Y);
    }
}

int main () {
    scanf("%d%d%d%d", &N, &L, &X, &Y);
    for (int i = 0; i < N; i++)
        scanf("%d", &A[i]);
    solve();
    return 0;
}