POJ1029 C++解法_C/C++_编程开发_程序员俱乐部

/*  poj 1029 False coin

    题目大意:
        同1013，查找假的硬币。不过不同的是，不要求求出假币是重还是轻，只需要找出即可。

    解题思路:
        同1013.

        令所有出现在左侧的硬币为1，右侧的硬币为-1，称重结果: 左侧重为1，轻为-1。

        则有如下

            a、假币较重，其每次的结果与称重结果完全相同 -- 左侧时都为1，右侧时都为-1

            b、假币较轻，其每次的结果与称重结果完全相同 -- 左侧时其为1，结果-1；右侧反过来

        则最后，只有真正的假币会与所有的测试结果完全相同或者相反 -- 重相同，轻相反。
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>

namespace {
    using namespace std;

    const int N_MAX = 1000;//硬币允许最多总个数
    const int K_MAX = 100;//硬币比较允许最多次数

    int C[N_MAX+1][K_MAX]; // 记录每枚硬币每次的假设结果
    int R[K_MAX]; // 记录真实称重结果
}

int main()
{
    int N, K;

    //freopen("1.txt","r",stdin);
    scanf("%d%d", &N, &K);

    int t;
    for (int i=0; i<K; i++)
    {
        int Pi;
        scanf("%d", &Pi);
        for (int j=0; j<Pi; j++)
        {
            scanf("%d", &t);
            C[t][i] = 1;    // 左侧假设为1
        }
        for (int j=0; j<Pi; j++)
        {
            scanf("%d", &t);
            C[t][i] = -1;   // 右侧假设为-1
        }

        char rs[8];
        scanf("%s", rs);

        // 本次称重结果
        if (rs[0]=='<') R[i]=-1;
        if (rs[0]=='=') R[i]= 0;
        if (rs[0]=='>') R[i]= 1;
    }

    bool bFound = true;
    int k=0;
    for (int i=1 ; i<=N; i++)
    {
        int c1=0, c2=0;
        for (int j=0; j<K; j++)
        {
            if (C[i][j] == R[j]) // 同为1或-1或0的情况
                ++c1;

            if (C[i][j] == -R[j]) // 同为0或者一个1、一个-1的情况
                ++c2;

            if (C[i][j]!=R[j] && C[i][j]!=-R[j]) // 一个为0一个不为0的情况
                break;
        }

        if (c1==K || c2==K) // 存在完全相同或者完全相反的情况，注意0同属于两种i情况
        {
            if(k==0)
            {
                k = i; // 首次找到这种情况，记录之
            }
            else
            {
                bFound = false; // 多于一次找到，说明不可判断，停止查找
                break;
            }
        }
    }

    if (bFound)
        printf("%d\n", k);
    else
        printf("0\n");

    return 0;
}

?