窗口

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

扫描命中点击点的窗口并选择最高层，用递增层次编号模拟被选窗口置顶。

OJ: shumeng

题目 ID: CSP201403B

难度:入门

标签:模拟数组

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 样例窗口层次变化
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

有 NN 个边与坐标轴平行的窗口，边界上的点也属于该窗口。按输入顺序给出从最下层到最顶层的窗口。每次点击输出被点击点所在的最顶层窗口编号，并把该窗口移到最顶层（其余窗口层次不变）；没有命中窗口时输出 IGNORED。

思路

朴素解显式维护从底到顶的窗口顺序：

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:50
 */
// brute.cpp：小数据暴力解，显式维护从底到顶的窗口顺序。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n, m;
int left_x[MAXN], bottom_y[MAXN], right_x[MAXN], top_y[MAXN];
int order[MAXN];

bool contains(int id, int x, int y) {
    return left_x[id] <= x && x <= right_x[id] && bottom_y[id] <= y && y <= top_y[id];
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> left_x[i] >> bottom_y[i] >> right_x[i] >> top_y[i];
        order[i] = i;
    }

    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;

        int position = 0;
        for (int j = n; j >= 1; j--) {
            if (contains(order[j], x, y)) {
                position = j;
                break;
            }
        }

        if (position == 0) {
            cout << "IGNORED\n";
            continue;
        }

        int chosen = order[position];
        cout << chosen << '\n';
        for (int j = position; j < n; j++) {
            order[j] = order[j + 1];
        }
        order[n] = chosen;
    }

    return 0;
}

本题也可只记录每个窗口的层次编号。初始窗口 i 的层次为 i；每次点击扫描所有窗口，在包含该点的窗口中找 level 最大者。选中后把它的层次设为新的最大值，其余窗口层次不变，正好等价于把它置顶。

判断点在矩形中时四条边都要包含：left_x<=x<=right_x 且 bottom_y<=y<=top_y。

样例窗口层次变化

下表的窗口顺序从底到顶排列；命中窗口会被移动到最右端：

点击 点击前顺序 命中窗口 点击后顺序
(1, 1) [1, 2, 3] 2 [1, 3, 2]
(0, 0) [1, 3, 2] 1 [3, 2, 1]
(4, 4) [3, 2, 1] 1 [3, 2, 1]
(0, 5) [3, 2, 1] IGNORED [3, 2, 1]

第一次点击使窗口 2 从中间升到顶层。第二次点击后窗口 1 成为顶层，所以第三次重叠点击仍选择窗口 1。 最后一次没有命中窗口，因此顺序完全不变。

代码

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:50
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n, m;
int left_x[MAXN], bottom_y[MAXN], right_x[MAXN], top_y[MAXN];
int level[MAXN];

bool contains(int id, int x, int y) {
    return left_x[id] <= x && x <= right_x[id] && bottom_y[id] <= y && y <= top_y[id];
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> left_x[i] >> bottom_y[i] >> right_x[i] >> top_y[i];
        level[i] = i;
    }

    int top_level = n;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;

        int chosen = 0;
        for (int id = 1; id <= n; id++) {
            if (contains(id, x, y) && (chosen == 0 || level[id] > level[chosen])) {
                chosen = id;
            }
        }

        if (chosen == 0) {
            cout << "IGNORED\n";
        } else {
            cout << chosen << '\n';
            top_level++;
            level[chosen] = top_level;
        }
    }

    return 0;
}

复杂度

每次点击扫描所有窗口，时间复杂度为 O(NM)O(NM)，空间复杂度为 O(N)O(N)。

总结

窗口置顶的本质是维护全序。对于小规模模拟，可以显式移动顺序；也可以给被选窗口一个新的最大层次编号。