P5995题解

Up_Xu · 2023-08-14 20:55:18 · 题解

题意

给出 n 个制镜厂各自所能制造镜子的最小宽度、最大宽度、最小高度、最大高度， 求是否有制镜厂能制出所有其它制镜厂能制出的镜子。

思路

若有一家制镜厂 i 能制出所有其它制镜厂能制出的镜子，就说明此制镜厂所制镜子的最小宽度 w1_i 为所有厂制镜最小宽度的最小值，最大宽度 w2_i 为所有厂制镜最大宽度的最大值，最小高度 h1_i 为所有厂制镜最小高度的最小值，最大高度 h2_i 为所有厂制镜最大高度的最大值。

这么一想，本题就超级简单了。求出所有制镜厂制镜最小宽度的最小值 mw1，制镜最大宽度的最大值 mw2，制镜最小高度的最小值 mh1，以及制镜最大高度的最大值 mh2。然后枚举每家制镜厂，看是否有一家的最小宽度与 mv1 相等，最大宽度与 mv2 相等，最小高度与 mh1 相等，最大高度与 mh2 相等即可。

代码

#include <bits/stdc++.h>
#define M 100010
using namespace std;
int T,n;
int w1[M],w2[M],h1[M],h2[M],mw1,mh1,mw2,mh2;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);//加速代码 
    cin>>T;
    while(T--){
        cin>>n;
        mw1=mh1=1e9;mw2=mh2=0;//先赋上最大值与最小值 
        for(int i=1;i<=n;i++){
            cin>>w1[i]>>w2[i]>>h1[i]>>h2[i];
            mw1=min(mw1,w1[i]);//求最小宽度的最小值
            mw2=max(mw2,w2[i]);//求最大宽度的最大值
            mh1=min(mh1,h1[i]);//求最小高度的最小值
            mh2=max(mh2,h2[i]);//求最大高度的最大值
        }
        int flag=1;
        for(int i=1;i<=n;i++)
            if(w1[i]==mw1&&w2[i]==mw2&&h1[i]==mh1&&h2[i]==mh2){//判断是否都相等 
                cout<<"TAK\n";
                flag=0;
                break;
            }
        if(flag)cout<<"NIE\n";
    }
}