回收站选址

GitHub跳转原题关系图Canvas 关系图返回列表

用坐标集合判断四个正交邻居和四个对角邻居，按对角垃圾数计分。

OJ: shumeng

题目 ID: CSP201912B

难度:入门

标签:模拟集合坐标

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 朴素做法
    2. 坐标集合查询
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

平面上有 nn 个互不相同的整数坐标点（垃圾点）。一个点 (x,y)(x,y) 可作为回收站选址，当且仅当上下左右四个相邻位置 (x±1,y), (x,y±1)(x\pm 1,y),\ (x,y\pm 1) 都有垃圾。此时它的得分等于四个对角位置 (x±1,y±1)(x\pm 1,y\pm 1) 中有垃圾的位置数。统计得分为 0,1,2,3,40,1,2,3,4 的选址个数。

思路

朴素做法

对每个垃圾点都扫描全部坐标，线性检查它需要的八个邻居。时间复杂度 O(n2)O(n^2)，作为对拍基准。

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:41
 */
// brute.cpp：小数据暴力解，对每个候选点扫描所有垃圾坐标，检查八个相邻位置。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n;
long long point_x[MAXN], point_y[MAXN];

// 线性扫描全部垃圾坐标，判断 (x, y) 处是否有垃圾。
bool has_point(long long x, long long y) {
    for (int i = 1; i <= n; i++) {
        if (point_x[i] == x && point_y[i] == y) return true;
    }
    return false;
}

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

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

    int answer[5] = {};
    for (int i = 1; i <= n; i++) {
        long long x = point_x[i], y = point_y[i];
        // 先确认四个正交邻居，再统计四个对角邻居作为得分。
        if (!has_point(x - 1, y) || !has_point(x + 1, y)
                || !has_point(x, y - 1) || !has_point(x, y + 1)) {
            continue;
        }
        int score = 0;
        score += has_point(x - 1, y - 1);
        score += has_point(x - 1, y + 1);
        score += has_point(x + 1, y - 1);
        score += has_point(x + 1, y + 1);
        answer[score]++;
    }
    for (int i = 0; i <= 4; i++) cout << answer[i] << '\n';

    return 0;
}

坐标集合查询

把所有坐标放入集合。每个候选点只做 8 次集合查询：先确认四个正交邻居，成立后统计四个对角邻居，得到分数并计数。坐标范围很大且可以为负，所以使用 long long 保存坐标。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:41
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n;
long long point_x[MAXN], point_y[MAXN]; // 各垃圾点坐标
set<pair<long long, long long> > points; // 坐标集合，用于 O(log n) 查询某个位置是否有垃圾

// 判断坐标 (x, y) 处是否存在垃圾。
bool has_point(long long x, long long y) {
    return points.find(make_pair(x, y)) != points.end();
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> point_x[i] >> point_y[i];
        points.insert(make_pair(point_x[i], point_y[i]));
    }

    int answer[5] = {}; // 得分为 0..4 的回收站选址个数
    for (int i = 1; i <= n; i++) {
        long long x = point_x[i], y = point_y[i];
        // 上下左右四个正交邻居必须全部存在垃圾。
        if (!has_point(x - 1, y) || !has_point(x + 1, y)
                || !has_point(x, y - 1) || !has_point(x, y + 1)) {
            continue;
        }
        // 评分：四个对角位置中有几处存在垃圾。
        int score = 0;
        score += has_point(x - 1, y - 1);
        score += has_point(x - 1, y + 1);
        score += has_point(x + 1, y - 1);
        score += has_point(x + 1, y + 1);
        answer[score]++;
    }
    for (int i = 0; i <= 4; i++) cout << answer[i] << '\n';

    return 0;
}

复杂度

  • 时间：集合构建和每次查询为 O(log⁡n)O(\log n)，总时间复杂度 O(nlog⁡n)O(n\log n)。
  • 空间：O(n)O(n)。

总结

小范围几何邻居判断不需要建网格。将实际出现的坐标存为集合后，平移八个固定方向逐一查询即可。