POJ 1029 false coin题目链接 一堆硬币中有且仅有一枚假币，假币质量与其他币不等，根据给出的等式或不等式，判断哪一枚是假币，也有可能无法判断是否有假币
等式两边的必须是真币不等式中一定有假币，且每一个不等式中，假币只会一直在大于的那边或者一直在小于的那边 normal set 记录正常的币，light 数组记录币在不等式中小的次数，heavy 数组记录币在不等式中大的次数light/heavy中次数 = 不等式次数的，且不在normal set中的，且只有1个币符合这两个条件，那么就是答案注意分析不等式次数==0的情况
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<set> using namespace std; vector<int> t(1001); vector<int> ans; set<int> normal; int main() { int n, k, unequal=0; scanf("%d%d", &n, &k); int light[n+1]; int heavy[n+1]; memset(light, 0, sizeof(light)); memset(heavy, 0, sizeof(heavy)); for(int i = 0; i<k; i++){ int num; scanf("%d", &num); for(int j = 0; j<2*num; j++){ int temp; scanf("%d", &temp); t[j] = temp; } char ch; while((ch=getchar())!='=' && ch!='>' && ch!='<'); if(ch=='='){ for(int j = 0; j<2*num; j++) normal.insert(t[j]); } else{ unequal++; if(ch=='<'){ for(int j = 0; j<num; j++) light[t[j]] = light[t[j]] + 1; for(int j = num; j<2*num; j++) heavy[t[j]] = heavy[t[j]] + 1; } else if(ch=='>'){ for(int j = 0; j<num; j++) heavy[t[j]] = heavy[t[j]] + 1; for(int j = num; j<2*num; j++) light[t[j]] = light[t[j]] + 1; } } } set<int>::iterator pg = normal.begin(); while(pg != normal.end()){ light[*pg]=unequal+1; heavy[*pg]=unequal+1; pg++; } for(int i = 1; i<=n; i++){ if(light[i]==unequal) ans.push_back(i); if(heavy[i]==unequal) ans.push_back(i); } int res = 0; if(ans.size()==1){ res = ans[0]; } else if(ans.size()==2){ if(ans[0]==ans[1]&&unequal==0) res = ans[0]; } cout<<res<<endl; return 0; }