自动搬运

查看原文

来自洛谷，原作者为

	Sweet_2013 今夕是何年？ | 234粉爆我妹的照片，求关 | 互关条件 /training/813543

搬运于2025-08-24 23:02:28，当前版本为作者最后更新于2024-12-21 23:52:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我的思考过程：

这道题的考点是贪心，双指针，扫描线，优先队列。

题面翻译：

给我们 $n$ 个圆以及一个矩形，问我们在采取最优的放置矩形的策略下，完全在矩形范围内的圆的个数。

做法：

首先对于矩形的放置，我们有两个维度需要考虑—— $x$ 和 $y$。因此我们需要先固定一维，然后枚举另一个维度，这就是扫描线的体现。

但是，我们发现 $x$，$y$ 的范围是令人蛋疼的 $10^8$，不能直接暴力枚举。

那怎么固定呢？其实仔细思考一下，在最优的矩形放置策略中，我们是不是将矩形的底部刚好与某个圆的底部相切是最优的。其实显然，因为上诉操作会尽可能的留空间给上面的圆形（这也是我认为考点有贪心的点）。因此，对于固定的 $y$，我们只需要枚举每个圆的最底部即可。

可以先将圆按照右端点升序排序，然后双指针，对于 $x$ 这个维度我们也需要像维度 $y$ 一样贪心地考虑。

因此，我们需要用一个优先队列对在矩形中的圆的最左端点进行维护，这样在遍历右端点的时候我们可以及时且高效地将左端点越出矩形左边界的点删除。然后依次遍历维护最大点数（优先队列的大小的最大值）即可。

附上代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x, y, r;
    bool operator <(node a){
        return x + r < a.x + a.r;
    }
}p[1001];
int ys[1001], n, w, h, ans;
int slv(int ed){
    priority_queue<int, vector<int>, greater<int>>q;
    int ans = 0;
    for(int i = 0; i < n; i++){
        //invalid
        if(p[i].y - p[i].r < ed || p[i].y + p[i].r > h + ed)continue;
        if(2 * p[i].r > w)continue;
        int last = p[i].x + p[i].r;
        while(q.size() && last - q.top() > w) q.pop();        
        int l = p[i].x - p[i].r;
        q.push(l);
        ans = max(ans, (int)q.size());
    }
    return ans;
} 
int main(){
    cin >> n >> w >> h;
    for(int i = 0; i < n; i++){
        cin >> p[i].x >> p[i].y >> p[i].r;
        ys[i] = p[i].y - p[i].r;
    }
    sort(p, p + n);
    sort(ys, ys + n);
    for(int i = 0; i < n; i++) ans = max(ans, slv(ys[i]));
    swap(w, h);
    for(int i = 0; i < n; i++) ans = max(ans, slv(ys[i]));
    cout << ans << endl;
    return 0;
}