专栏文章

题解:P13474 [GCJ 2008 APAC SemiFinal] What are Birds?

P13474题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minw29d0
此快照首次捕获于
2025/12/02 09:17
3 个月前
此快照最后确认于
2025/12/02 09:17
3 个月前
查看原文

题目链接

Solution

分析

给定一系列已知鸟类和非鸟类的动物数据(包含身高和体重),以及一些未知动物的数据,需要判断每个未知动物属于以下哪类:
  1. 在鸟类边界内 BIRD
  2. 在边界外但扩展范围无冲突 UNKNOWN
  3. 在边界外且扩展范围有冲突 NOT BIRD

实现步骤

  1. 计算所有鸟类的最小/最大身高 (minH/maxH)(minH/maxH)
  2. 计算所有鸟类的最小/最大体重 (minW/maxW)(minW/maxW)
  3. 判定。

AC代码

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

struct stu {
    int height;
    int weight;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int c;
    cin >> c;
    for (int num = 1; num <= c; num++) {
        int n;
        cin >> n;
        vector<stu> birds;
        vector<stu> notBirds;
        //设置最值
        int minh = INT_MAX;
        int maxh = INT_MIN;
        int minw = INT_MAX;
        int maxw = INT_MIN;
        for (int i = 1; i <= n; i++) {
            int h, w;
            string part1, part2;
            cin >> h >> w >> part1;
            if (part1 == "BIRD") {
                birds.push_back({h, w});
                minh = min(minh, h);
                maxh = max(maxh, h);
                minw = min(minw, w);
                maxw = max(maxw, w);
            } 
            else if (part1 == "NOT") {
                cin >> part2; // 读取后面的"BIRD"
                notBirds.push_back({h, w});
            }
        }
        int m;
        cin >> m;
        vector<stu> unknowns(m);
        for (int i = 0; i < m; i++) {
            cin >> unknowns[i].height >> unknowns[i].weight;
        }
        cout << "Case #" << num << ":\n";
        for (auto a : unknowns) {
            if (birds.empty()) {
                cout << "UNKNOWN\n";
                continue;
            }
            if (a.height >= minh && a.height <= maxh && 
                a.weight >= minw && a.weight <= maxw) {
                cout << "BIRD\n";
                continue;
            }
            int minhh = min(minh, a.height);
            int maxhh = max(maxh, a.height);
            int minww = min(minw, a.weight);
            int maxww = max(maxw, a.weight);
            
            bool flag = false;
            for (auto n : notBirds) {
                if (n.height >= minhh && n.height <= maxhh &&
                    n.weight >= minww && n.weight <= maxww) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                cout << "NOT BIRD\n";
            } 
            else {
                cout << "UNKNOWN\n";
            }
        }
    }
    return 0;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...