他来了

他来了

育华周赛,他带着奶茶来了

他也许没有奶茶

但他一定有好题

• 本期主题二分

T1

第k小整数 题解

题目分析

本题要求找出 $n$ 个正整数中第 $k$ 小的整数，其中相同大小的整数只计算一次。

核心思路

1. 去重：由于相同大小的整数只计算一次，我们需要对数据进行去重处理
2. 排序：将去重后的数据从小到大排序
3. 查找第 k 小：找到排序后数组中的第 $k$ 个元素

解题步骤

方法一：使用 set 自动去重 + 排序

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    
    set<int> s;  // set 会自动去重并排序
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        s.insert(x);
    }
    
    // 判断是否有第 k 小的数
    if (k > (int)s.size()) {
        cout << "NO RESULT" << endl;
    } else {
        // 遍历 set 找到第 k 个元素
        auto it = s.begin();
        advance(it, k - 1);  // 移动到第 k 个位置
        cout << *it << endl;
    }
    
    return 0;
}

方法二：排序 + unique 去重

#include <bits/stdc++.h>
using namespace std;

const int N = 10050;
int a[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    
    // 先排序
    sort(a+1, a + n+1);
    
    // 去重
    int cnt = unique(a+1, a + n+1) - a;  // unique 返回去重后的末尾位置
    
    // 判断是否有第 k 小的数
    if (k > cnt) {
        cout << "NO RESULT" << endl;
    } else {
        cout << a[k] << endl;  
    }
    
    return 0;
}

方法三：桶排序（计数排序）

由于题目中给出数值范围 $< 30000$，我们可以使用桶排序（计数排序）来解决。

#include <bits/stdc++.h>
using namespace std;

const int MAX_VAL = 30050;  // 最大值 + 50
bool bucket[MAX_VAL];  // 桶数组，标记数字是否出现过

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    
    // 清空桶
    memset(bucket, false, sizeof(bucket));
    
    // 将数字放入对应的桶中
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        bucket[x] = true;  // 标记该数字出现过
    }
    
    // 从小到大遍历桶，找到第 k 个出现的数字
    int cnt = 0;  // 计数器
    for (int i = 1; i < MAX_VAL; ++i) {
        if (bucket[i]) {  // 如果这个桶有数字
            cnt++;
            if (cnt == k) {  // 找到第 k 个
                cout << i << endl;
                return 0;
            }
        }
    }
    
    // 如果没有找到
    cout << "NO RESULT" << endl;
    
    return 0;
}

桶排序的优势：

• 时间复杂度为 $O(n + M)$，其中 $M$ 是数值范围的最大值
• 当数值范围较小时，效率非常高
• 天然具有去重功能（每个桶只标记是否出现）

T2

2/3次方根 题解

核心思路

1. 二分答案法：通过二分查找找到满足条件的最大整数

• 因为是向下取整,所以mid * mid * mid <= n * n,由此可知取<=成立的情况下的右边界,或者取>成立的情况下的左边界的左边一位

::: warning 此方法在计算 mid * mid * mid 和 n * n 时会发生溢出！

• 1. 转化成__int128
• 2. 转化成mid* sqrt(mid) <= n
     :::

解题步骤

方法一：二分答案法（<=成立下的右边界）

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n;
    cin >> n;
    
    // 我们要找最大的 x，使得 x^3 <= n^2
    // 二分答案的范围是 [0, n]
    ll left = 0, right = n;
    ll ans = 0;
    
    while (left <= right) {
        ll mid = (left + right) / 2;
    //  ll cube = mid * mid * mid;  // ❌ 当 mid > 2*10^6 时会溢出
     // ll target = n * n;          // ❌ 当 n > 3*10^9 时会溢出
        
        if (mid* sqrt(mid) <= n) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

T3

物品分组 题解

题目分析

本题要求将 $n$ 个物品分成 $k$ 组（保持顺序），使得各组价值之和的最大值最小。

这是一个经典的二分答案 + 贪心验证问题。

核心思路

为什么想到二分答案？

1. 答案具有单调性：如果某个最大值 $X$ 可行，那么所有大于 $X$ 的值也都可行
2. 易于验证：给定一个上限 $X$，我们可以用贪心法快速判断是否能分成 $k$ 组
3. 最值问题：题目要求"最大值尽可能小"，符合二分答案的典型特征

验证策略（贪心）

给定一个上限 $max\_val$，判断能否将物品分成不超过 $k$ 组，使得每组的和都不超过 $max\_val$：

• 从左到右遍历物品
• 尽可能多地将物品放入当前组，直到再加一个就会超过 $max\_val$
• 开启新的一组，继续上述过程
• 最后统计使用的组数是否 $\leq k$

解题步骤

方法一：二分答案 + 贪心验证（推荐 ⭐⭐⭐）

#include <bits/stdc++.h>
using namespace std;

const int N = 1050;
int n, k;
int a[N];

// 检查是否能在每组和不超过 mid 的情况下分成不超过 k 组
bool check(int mid) {
    int cnt = 1;  // 当前组数
    int sum = 0;  // 当前组的和
    
    for (int i = 1; i <= n; ++i) {
        // 如果单个物品就超过限制，直接返回 false
        if (a[i] > mid) return false;
        
        // 如果加上当前物品会超过限制，开启新的一组
        if (sum + a[i] > mid) {
            cnt++;
            sum = a[i];
        } else {
            sum += a[i];
        }
    }
    
    return cnt <= k;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> k;
    
    int max_val = 0, sum = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        max_val = max(max_val, a[i]);
        sum += a[i];
    }
    
    cin >> k;
    
    // 二分答案的范围：[最大单个物品价值，所有物品总价值]
    int l = max_val, r = sum;
    int ans = sum;
    
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;  // 尝试更小的值
        } else {
            l = mid + 1;  // 需要更大的值
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

T4

奶牛炸弹 题解

题目分析

本题要求在数轴上的 $N$ 个位置放置干草，使用 $K$ 头威力为 $R$ 的奶牛引爆所有干草，求 $R$ 的最小值。

这是一个经典的二分答案 + 贪心验证问题。

核心思路

为什么想到二分答案？

1. 答案具有单调性：如果威力 $R$ 可以引爆所有干草，那么所有大于 $R$ 的威力都可以
2. 易于验证：给定一个威力 $R$，我们可以用贪心法快速判断是否能用不超过 $K$ 头奶牛引爆所有干草
3. 最值问题：题目要求"最小值"，符合二分答案的典型特征

验证策略（贪心）

给定威力 $R$，判断能否用不超过 $K$ 头奶牛引爆所有干草：

• 首先将所有干草位置排序
• 从左到右遍历，每次选择最左边未引爆的干草
• 在这个干草右侧距离 $2R$ 的位置投放奶牛（这样能覆盖最多的右侧干草）
• 统计需要的奶牛数量是否 $\leq K$

贪心正确性：每次投放都尽可能向右延伸，这样能覆盖最多的后续干草。

解题步骤

方法一：二分答案 + 贪心验证

#include <bits/stdc++.h>
using namespace std;

const int N = 50050;
int n, k;
int x[N];  // 干草位置

// 检查威力为 R 时能否用不超过 k 头奶牛引爆所有干草
bool check(int R) {
    int cnt = 1;  // 已使用的奶牛数量
    int last = 1;  // 当前处理到的干草下标

    for(int i = 2; i <= n; ++i) {
        // 如果第i个干草超出了当前奶牛的覆盖范围
        if(x[i] - x[last] > 2 * R) {
            cnt++;
            last = i;
        }
    }
    return cnt <= k;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    for (int i = 1; i <= n; ++i) {
        cin >> x[i];
    }

    // 排序（关键！）
    sort(x+1, x + 1 + n);

    // 二分答案的范围：[0, 最大坐标差]
    int l = 0, r = x[n] - x[1];
    int ans = r;

    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;  // 尝试更小的威力
        } else {
            l = mid + 1;  // 需要更大的威力
        }
    }

    cout << ans << endl;

    return 0;
}

T5

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000010;

ll n, m;
ll a[N];
ll b[N]; // 1表示发工资了 0 表示没发工资
ll presum[N]; // 发工资的人的位置前缀和
ll precnt[N]; // 发工资的人的个数前缀和


bool check(ll mid) {
    for (int i = 1; i <= n; i++) {
        // 计算每个人的快乐值
        ll val = 0;
        // 计算左边获得的快乐值
        val += (mid - i) * (precnt[i - 1] - precnt[max(i - mid, 0ll)]) + (presum[i - 1] - presum[max(i - mid, 0ll)]);

        // 计算右边获得的快乐值
        val += (mid + i) * (precnt[min(i + mid, n)] - precnt[i]) - (presum[min(i + mid, n)] - presui]);

        // 加上自己的快乐值
        val += b[i] * mid;
        if (val < a[i]) {
            return false;
        }
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        b[x] = 1;
    }

    for (int i = 1; i <= n; i++) {
        presum[i] = presum[i - 1] + b[i] * i;
        precnt[i] = precnt[i - 1] + b[i];
    }

    ll l = 0, r = 1e12;
    ll ans = 0;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }

    cout << ans << endl;

    return 0;
}

T6

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;


///
struct Node {
    int l, r;
    bool operator<(const Node &other) const {
        return r > other.r;
    }
};

int n;
Node a[N];  // 干草位置


bool check(int mid) {

    priority_queue<Node> q;
    int last = 0;
    int idx = 1;
    while (last < 20000) {
        while (idx <= n && a[idx].l <= last + mid) {
            q.push(a[idx]);
            ++idx;
        }
        if (q.empty()) {
            break;
        }
        if ( q.top().l >=  last) {
            int offset = q.top().l - last;
            last = q.top().r -  offset;
            q.pop();
        }else {
            int offset = min(mid, last - q.top().l);
            last = offset +  q.top().r;
            q.pop();
        }

    }


    return  last >= 20000;

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i].l >> a[i].r;
        a[i].l *= 2;
        a[i].r *= 2;
    }

    sort(a+1, a + 1 + n, [](const Node &a, const Node &b) {
        return a.l < b.l;
    });

    int l = 0, r = 20000;
    int ans = r;

    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    cout << ans / 2.0 << endl;

    return 0;
}