美团 3.28 笔试真题 - 算法岗

import sys
import heapq
input = sys.stdin.readline

def main():
    n, a, b, k = map(int, input().split())
    x = list(map(int, input().split()))

    # 操作二固定减少 b * k
    total = sum(x)
    total -= b * k

    # 操作一：贪心，每次对当前最大元素执行 floor(x/2)
    # 用最大堆模拟
    heap = [-v for v in x]
    heapq.heapify(heap)

    for _ in range(a):
        val = -heapq.heappop(heap)
        reduced = val // 2
        total -= (val - reduced)
        heapq.heappush(heap, -reduced)

    print(total)

main()

import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.svm import OneClassSVM
from sklearn.metrics import roc_auc_score, f1_score

def solve(data, test_data, nu_list, gamma_list):
    """
    data: DataFrame，含特征列和 'label' 列（1=正常, -1=异常）
    test_data: DataFrame，待预测数据（无标签）
    nu_list: list of float，nu 候选值
    gamma_list: list of float/str，gamma 候选值
    """
    # Step 1: 分离正常样本与异常样本
    normal = data[data['label'] == 1].drop(columns=['label'])
    anomaly = data[data['label'] == -1].drop(columns=['label'])

    # Step 2: 划分正常数据为训练集和验证集
    X_train, X_val = train_test_split(
        normal, test_size=0.25, random_state=42
    )

    # Step 3: 标准化（仅在训练集上 fit）
    scaler = StandardScaler()
    X_train_scaled = scaler.fit_transform(X_train)
    X_val_scaled = scaler.transform(X_val)
    X_anomaly_scaled = scaler.transform(anomaly)

    # 构造验证集：正常验证集 + 异常数据
    X_eval = np.vstack([X_val_scaled, X_anomaly_scaled])
    y_eval = np.array([1] * len(X_val) + [-1] * len(anomaly))

    # Step 4 & 5: 网格搜索
    results = []
    for nu in nu_list:
        for gamma in gamma_list:
            clf = OneClassSVM(kernel='rbf', nu=nu, gamma=gamma)
            clf.fit(X_train_scaled)

            # decision_function 值越大越"正常"
            scores = clf.decision_function(X_eval)
            y_pred = clf.predict(X_eval)

            auc = roc_auc_score(y_eval, scores)
            f1 = f1_score(y_eval, y_pred)
            results.append((auc, f1, nu, gamma))

    # Step 6: 选择最优参数
    # AUC 降序, F1 降序, nu 升序, gamma 升序
    results.sort(key=lambda r: (-r[0], -r[1], r[2], r[3]))
    best_auc, best_f1, best_nu, best_gamma = results[0]

    print(f"Best params: nu={best_nu}, gamma={best_gamma}")
    print(f"AUC={best_auc:.4f}, F1={best_f1:.4f}")

    # Step 7: 用全部正常数据重新训练
    scaler_final = StandardScaler()
    X_all_normal = scaler_final.fit_transform(normal)
    X_test_scaled = scaler_final.transform(test_data)

    final_model = OneClassSVM(
        kernel='rbf', nu=best_nu, gamma=best_gamma
    )
    final_model.fit(X_all_normal)

    predictions = final_model.predict(X_test_scaled)
    return predictions

import sys
from bisect import bisect_left, insort
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    def enumerate_half(start, end):
        """
        枚举 [start, end) 天的所有方案。
        返回字典：skip_count -> sorted list of diff values
        """
        # states: list of (diff, skip_count)
        states = [(0, 0)]
        for i in range(start, end):
            new_states = []
            for diff, skips in states:
                # 选择 1：浇红树
                new_states.append((diff + a[i], skips))
                # 选择 2：浇黑树
                new_states.append((diff - b[i], skips))
                # 选择 3：跳过
                if skips < k:
                    new_states.append((diff, skips + 1))
            states = new_states

        # 按 skip_count 分组并排序
        from collections import defaultdict
        groups = defaultdict(list)
        for diff, skips in states:
            groups[skips].append(diff)
        for skips in groups:
            groups[skips].sort()
        return groups

    mid = n // 2
    left_groups = enumerate_half(0, mid)
    right_groups = enumerate_half(mid, n)

    ans = float('inf')

    for skip_r, diffs_r in right_groups.items():
        for diff2 in diffs_r:
            target = -diff2  # 希望 diff1 尽量接近 -diff2
            # 前半跳过次数 skip_l 需满足 skip_l + skip_r <= k
            max_skip_l = k - skip_r
            for skip_l in range(max_skip_l + 1):
                if skip_l not in left_groups:
                    continue
                arr = left_groups[skip_l]
                # 二分查找最接近 target 的值
                pos = bisect_left(arr, target)
                # 检查 pos 和 pos-1 两个候选位置
                for idx in (pos - 1, pos):
                    if 0 <= idx < len(arr):
                        ans = min(ans, abs(arr[idx] + diff2))

            if ans == 0:
                print(0)
                return

    print(ans)

main()

import sys
from math import log2
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))

    if n <= 1:
        print(0)
        return

    # Sparse Table 预处理：区间最大值的位置
    LOG = int(log2(n)) + 1 if n > 0 else 1
    sp = [[0] * n for _ in range(LOG + 1)]

    for i in range(n):
        sp[0][i] = i

    j = 1
    while (1 << j) <= n:
        i = 0
        while i + (1 << j) - 1 < n:
            l_idx = sp[j - 1][i]
            r_idx = sp[j - 1][i + (1 << (j - 1))]
            sp[j][i] = l_idx if a[l_idx] >= a[r_idx] else r_idx
            i += 1
        j += 1

    def query_max_pos(l, r):
        """返回 a[l..r] 中最大值的位置"""
        if l > r:
            return -1
        k = int(log2(r - l + 1))
        li = sp[k][l]
        ri = sp[k][r - (1 << k) + 1]
        return li if a[li] >= a[ri] else ri

    from bisect import bisect_left

    ans = 0

    def solve(L, R):
        nonlocal ans
        if L >= R:
            return

        m = query_max_pos(L, R)
        # 递归处理两侧
        solve(L, m - 1)
        solve(m + 1, R)

        # 统计跨越 m 的合法区间 [l, r]，l in [L, m], r in [m, R]
        # 条件：a[m] < a[l] + a[r]，即 a[l] > a[m] - a[r] 或等价地 a[r] > a[m] - a[l]
        left_len = m - L + 1
        right_len = R - m + 1

        if left_len <= right_len:
            # 枚举左侧 l，在右侧二分
            # 收集右侧的 a 值并排序
            right_vals = sorted(a[i] for i in range(m, R + 1))
            for l in range(L, m + 1):
                # 需要 a[r] > a[m] - a[l]，即 a[r] >= a[m] - a[l] + 1
                threshold = a[m] - a[l] + 1
                # 右侧中 >= threshold 的个数
                pos = bisect_left(right_vals, threshold)
                ans += len(right_vals) - pos
        else:
            # 枚举右侧 r，在左侧二分
            left_vals = sorted(a[i] for i in range(L, m + 1))
            for r in range(m, R + 1):
                threshold = a[m] - a[r] + 1
                pos = bisect_left(left_vals, threshold)
                ans += len(left_vals) - pos

    # 增加递归深度限制
    sys.setrecursionlimit(300000)
    solve(0, n - 1)
    print(ans)

main()