十五届决赛真题-套手镯

问题思路：

手镯可以用矩形的上下左右边界来描述，每个手镯都有一个左、右、下、上的边界。

目标是找出一个矩形区域，计算这个矩形内最多能容纳多少个手镯。矩形可以按两种方向摆放，宽×高或高×宽，因此需要考虑两种情形。

解决策略：

滑动窗口+优先队列：我们使用一个优先队列来存储当前在矩形范围内的手镯。通过滑动矩形的上下边界，并动态维护符合条件的手镯集合，计算出矩形内最多手镯数量。

排序：先根据手镯的右边界进行排序，这样可以方便地通过滑动窗口的方式检查哪些手镯能放进矩形。

核心算法：

通过外层循环，固定矩形的下边界（每次尝试一个不同的下边界），然后计算矩形的上边界。

内层循环遍历所有手镯，判断哪些手镯的上下边界在当前的矩形范围内。

使用优先队列存储当前上下边界内的手镯，左边界小于矩形右边界减去矩形宽度的手镯被移除。

最终计算在矩形内能容纳最多的手镯数量。

参考代码:

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

typedef long long ll;
const int N = 1e5 + 10;  // 定义数组大小的上限
const int MOD = 1e9 + 7;  // 常用的大质数MOD

ll n, w, h;  // n是手镯数量，w和h是矩形的宽度和高度

// 定义结构体Node表示一个手镯的四个边界
struct Node {
    int l, r, b, t;  // 左、右、下、上边界
    // 重载小于运算符，按照左边界从大到小排序，优先队列中会保持左边界从小到大排列
    bool operator< (const Node &u) const {
        return l > u.l;
    }
} a[N];

// solve函数：计算矩形区域内可以容纳最多的手镯数
int solve(int tw, int th) {
    int res = 0;  // 记录结果（最大手镯数）
    
    // 外层循环：固定矩形的下边界line
    for (int i = 0; i < n; i++) {
        int bottom = a[i].b;  // 当前手镯的下边界
        int top = bottom + th;  // 计算矩形的上边界
        
        priority_queue<Node> q;  // 优先队列，用来存储在当前上下边界之内的手镯
        
        // 内层循环：检查所有手镯是否在当前的上下边界范围内
        for (int j = 0; j < n; j++) {
            // 如果手镯的上下边界在当前矩形范围内
            if (a[j].b >= bottom && a[j].t <= top) {
                q.push(a[j]);  // 将符合条件的手镯加入优先队列
            }
            
            // 移除不再符合当前左右边界范围的手镯
            while (!q.empty() && q.top().l < a[j].r - tw) {
                q.pop();  // 移除左边界小于当前手镯右边界-矩形宽度的手镯
            }
            
            // 更新最大值，计算当前矩形内的手镯数量
            res = max(res, (int)q.size());
        }
    }
    
    return res;  // 返回最大手镯数
}

// cmp函数：按照手镯右边界从小到大排序
bool cmp(Node a, Node b) {
    return a.r < b.r;
}

int main() {
    cin >> n >> w >> h;  // 输入手镯数量n和矩形的宽度w和高度h
    
    // 输入每个手镯的坐标和半径，并计算出每个手镯的四个边界
    for (int i = 0; i < n; i++) {
        int x, y, r;
        cin >> x >> y >> r;  // 输入手镯的中心坐标(x, y)和半径r
        a[i].l = x - r;  // 计算左边界
        a[i].r = x + r;  // 计算右边界
        a[i].b = y - r;  // 计算下边界
        a[i].t = y + r;  // 计算上边界
    }
    
    sort(a, a + n, cmp);  // 根据右边界升序排序所有手镯
    
    // 分别尝试两种矩形方向，w x h 和 h x w
    int res1 = solve(w, h);
    int res2 = solve(h, w);
    
    // 输出两种方向中的最大手镯数
    cout << max(res1, res2) << endl;
    
    return 0;
}