首页 > 代码库 > 【set】bzoj3715 [PA2014]Lustra

【set】bzoj3715 [PA2014]Lustra

对每种属性开一个set,只要某个厂家符合该属性的最值,就加进set,最后判断是否有某个厂家在4个set里都存在即可。

 1 #include<cstdio> 2 #include<set> 3 using namespace std; 4 int T,a[4][100001],EX[4],n; 5 set<int>S[4]; 6 typedef set<int>::iterator ITER; 7 bool check(const int &x) 8 { 9     for(int i=1;i<4;i++)10       if(S[i].find(x)==S[i].end())11         return 0;12     return 1;13 }14 int main()15 {16     scanf("%d",&T);17     for(;T>0;T--)18       {19           EX[0]=EX[2]=2147483647;20           EX[1]=EX[3]=-2147483647;21           scanf("%d",&n);22           for(int i=1;i<=n;i++)23             for(int j=0;j<4;j++)24               scanf("%d",&a[j][i]);25           for(int i=1;i<=n;i++) EX[0]=min(EX[0],a[0][i]);26           for(int i=1;i<=n;i++) EX[2]=min(EX[2],a[2][i]);27           for(int i=1;i<=n;i++) EX[1]=max(EX[1],a[1][i]);28           for(int i=1;i<=n;i++) EX[3]=max(EX[3],a[3][i]);29           for(int i=0;i<4;i++)30             for(int j=1;j<=n;j++)31               if(a[i][j]==EX[i]) S[i].insert(j);32           for(ITER it=S[0].begin();it!=S[0].end();it++)33             if(check(*it))34               {35                 puts("TAK");36                 goto OUT;37               }38           puts("NIE");39           OUT:for(int i=0;i<4;i++) S[i].clear();40       }41     return 0;42 }

 

【set】bzoj3715 [PA2014]Lustra