首页 > 代码库 > 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 <cstdio>
#include <cstring>
#include <algorithm>

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

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