美团 5.9 笔试真题 - 算法岗

import sys
input = sys.stdin.readline

def solve():
    T = int(input())
    out = []
    for _ in range(T):
        n, d = map(int, input().split())
        a = list(map(int, input().split()))
        cur = 1
        best = 1
        for i in range(1, n):
            if abs(a[i] - a[i - 1]) <= d:
                cur += 1
                if cur > best:
                    best = cur
            else:
                cur = 1
        out.append(str(best))
    print("\n".join(out))

solve()

import json
import numpy as np

data = json.loads(input())
train = np.array(data["train"], dtype=np.float64)
val = np.array(data["val"], dtype=np.float64)
test = np.array(data["test"], dtype=np.float64)

X_train, y_train = train[:, :-1], train[:, -1]
X_val, y_val = val[:, :-1], val[:, -1]
X_test = test

mu = X_train.mean(axis=0)
sigma = X_train.std(axis=0, ddof=0)
sigma = np.where(sigma == 0, 1.0, sigma)
X_train = (X_train - mu) / sigma
X_val = (X_val - mu) / sigma
X_test = (X_test - mu) / sigma

N, d = X_train.shape
w = np.zeros(d)
b = 0.0
m_w = np.zeros(d); v_w = np.zeros(d)
m_b = 0.0; v_b = 0.0

beta1, beta2, eps_adam = 0.9, 0.999, 1e-8
lam = 1e-4
base_lr = 0.01
bs = 16
eps_log = 1e-15

np.random.seed(42)
best_loss = float('inf')
best_w = w.copy()
best_b = b
no_improve = 0
t_step = 0

for epoch in range(1, 101):
    lr = base_lr * epoch / 5.0 if epoch <= 5 else base_lr
    perm = np.random.permutation(N)
    Xs = X_train[perm]
    ys = y_train[perm]

    for i in range(0, N, bs):
        xb = Xs[i:i + bs]
        yb = ys[i:i + bs]
        nb = xb.shape[0]

        z = xb @ w + b
        p = 1.0 / (1.0 + np.exp(-z))

        grad_w = xb.T @ (p - yb) / nb + lam * w
        grad_b = np.mean(p - yb)

        t_step += 1
        m_w = beta1 * m_w + (1 - beta1) * grad_w
        v_w = beta2 * v_w + (1 - beta2) * (grad_w * grad_w)
        m_b = beta1 * m_b + (1 - beta1) * grad_b
        v_b = beta2 * v_b + (1 - beta2) * (grad_b * grad_b)

        bc1 = 1.0 - beta1 ** t_step
        bc2 = 1.0 - beta2 ** t_step

        w -= lr * (m_w / bc1) / (np.sqrt(v_w / bc2) + eps_adam)
        b -= lr * (m_b / bc1) / (np.sqrt(v_b / bc2) + eps_adam)

    z_v = X_val @ w + b
    p_v = 1.0 / (1.0 + np.exp(-z_v))
    p_v = np.clip(p_v, eps_log, 1.0 - eps_log)
    cur_loss = -np.mean(y_val * np.log(p_v) + (1.0 - y_val) * np.log(1.0 - p_v)) \
               + 0.5 * lam * np.dot(w, w)

    if cur_loss < best_loss - 1e-6:
        best_loss = cur_loss
        best_w = w.copy()
        best_b = b
        no_improve = 0
    else:
        no_improve += 1
        if no_improve >= 10:
            break

w, b = best_w, best_b
z = X_test @ w + b
p = 1.0 / (1.0 + np.exp(-z))
labels = (p >= 0.5).astype(int)
print(json.dumps(labels.tolist()))

import sys
input = sys.stdin.readline

def feasible(a, n, m, G):
    if G == 0:
        return True
    bad = []
    for i in range(n - 1):
        if a[i + 1] - a[i] < G:
            bad.append(i)
            if len(bad) > 2:
                return False
    if not bad:
        return True

    if len(bad) == 1:
        cands = (bad[0], bad[0] + 1)
    elif len(bad) == 2 and bad[1] == bad[0] + 1:
        cands = (bad[0] + 1,)
    else:
        return False

    for k in cands:
        if 0 < k < n - 1 and a[k + 1] - a[k - 1] < G:
            continue
        if any(i != k - 1 and i != k for i in bad):
            continue

        first = a[1] if k == 0 else a[0]
        last = a[n - 2] if k == n - 1 else a[n - 1]

        if first - G >= 1:
            return True
        if last + G <= m:
            return True
        if 0 < k < n - 1 and a[k + 1] - a[k - 1] >= 2 * G:
            return True
        for i in range(n - 1):
            if i == k - 1 or i == k:
                continue
            if a[i + 1] - a[i] >= 2 * G:
                return True
    return False

def solve():
    T = int(input())
    out = []
    for _ in range(T):
        n, m = map(int, input().split())
        a = sorted(map(int, input().split()))
        lo, hi = 0, m
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if feasible(a, n, m, mid):
                lo = mid
            else:
                hi = mid - 1
        out.append(str(lo))
    print("\n".join(out))

solve()

import sys
from bisect import bisect_left

input = sys.stdin.readline
INF = 10 ** 18

def solve():
    n, D, E, L = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()

    b = [a[i] - E * i for i in range(n)]

    order = sorted(range(n), key=lambda i: (b[i], i))
    pos_to_rank = [0] * n
    for r, i in enumerate(order):
        pos_to_rank[i] = r
    sorted_b = [b[i] for i in order]

    size = 1
    while size < max(n, 1):
        size *= 2
    seg = [INF] * (2 * size)

    def update(rk, val):
        rk += size
        seg[rk] = val
        rk //= 2
        while rk:
            nv = min(seg[2 * rk], seg[2 * rk + 1])
            if seg[rk] == nv:
                break
            seg[rk] = nv
            rk //= 2

    def query(lo, hi):
        res = INF
        lo += size
        hi += size + 1
        while lo < hi:
            if lo & 1:
                if seg[lo] < res:
                    res = seg[lo]
                lo += 1
            if hi & 1:
                hi -= 1
                if seg[hi] < res:
                    res = seg[hi]
            lo >>= 1
            hi >>= 1
        return res

    f = [INF] * (n + 1)
    f[0] = 0
    for j in range(n):
        if j - L >= 0:
            update(pos_to_rank[j - L], INF)
        update(pos_to_rank[j], f[j])
        thr = b[j] - D
        lo_idx = bisect_left(sorted_b, thr)
        if lo_idx < n:
            res = query(lo_idx, n - 1)
            if res < INF:
                f[j + 1] = res + 1
    return f[n]

T = int(input())
out = []
for _ in range(T):
    out.append(str(solve()))
print("\n".join(out))