算法学习之路|称量硬币（模拟）

有一堆硬币，其中有一枚是假的，可能更轻也可能更重，用天平在两边放上相同数量的硬币，找出假币。

输入格式：第一行两个数N，K，表示硬币数和称量次数。接下来2K行，第一行第一个数表示天平两边硬币个数n，后2n个数为两边硬币编号，第二行为>,<或=符号

输出格式：如果不能判断哪个硬币是假的，输出0，能就输出硬币编号。

输入样例：
5 3
2 1 2 3 4
<
1 1 4
=
1 2 5
=

输出样例：
3

解题思路：用equal数组标记没问题的硬币（两边重量相同则硬币一定都是合格的）
用l和h数组分别标记称量出较轻和较重的硬币，l和h标记相等的说明硬币出现在轻的一侧和重的一侧的次数相等，硬币是合格的，否则是不合格的。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n,k,equ[1050],l[1050],h[1050],flag[1050],tmp[1050];
int main()
{
    scanf("%d%d",&n,&k);
    memset(equ,0,sizeof(equ));
    memset(l,0,sizeof(l));
    memset(h,0,sizeof(h));
    memset(tmp,0,sizeof(tmp));
    for (int i=1;i<=k;i++)
    {
        int x;
        char ch;
        scanf("%d",&x);
        for(int j=0;j<2*x;j++)
            scanf("%d",&tmp[j]);
        ch=getchar();
        while(ch!='=' && ch!='<' && ch!='>')
        {
            ch=getchar();
        }
        if(ch=='<')
        {
            for(int j=0;j<x;j++)
                l[tmp[j]]=1;
            for(int j=x;j<2*x;j++)
                h[tmp[j]]=1;
            for(int j=1;j<=n;j++)
            {
                bool flag=true;
                for(int k=0;k<2*x;k++)
                    if(j==tmp[k])
                    {
                        flag=false;
                        break;
                    }
                if(flag)
                    equ[j]=1;
            }
        }
        else if(ch=='=')
        {
            for(int j=0;j<2*x;j++)
                equ[tmp[j]]=1;
        }
        else if(ch=='>')
        {
            for(int j=0;j<x;j++)
                h[tmp[j]]=1;
            for(int j=x;j<2*x;j++)
                l[tmp[j]]=1;
            for(int j=1;j<=n;j++)
            {
                bool flag=true;
                for(int k=0;k<2*x;k++)
                    if(j==tmp[k])
                    {
                        flag=false;
                        break;
                    }
                if(flag)
                    equ[j]=1;
            }
        }
    }
    int ans,cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(equ[i])
            continue;
        if(l[i]&&h[i])
            continue;
        ans=i;
        cnt++;
    }
    if(cnt>1)
        printf("0\n");
    else
        printf("%d\n", ans);
    return 0;
}