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

· · 题解

题目链接

题目传送门

Solution

分析

给定一系列已知鸟类和非鸟类的动物数据（包含身高和体重），以及一些未知动物的数据，需要判断每个未知动物属于以下哪类：

  1. 在鸟类边界内 → BIRD。
  2. 在边界外但扩展范围无冲突 → UNKNOWN。
  3. 在边界外且扩展范围有冲突 → NOT BIRD。

    实现步骤

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

    AC代码

    
#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;

}