http://poj.org/problem?id=1029

因为只有一个假币,并且所有的不等式都是由假币造成的,因此每一个不等式都包含假币,且这颗假币会固定集中在不等式的轻端或者重端。
因此,我们可以开一个数组f,表示怀疑程度,对每一个不等式:
使重端的所有硬币++f[i]
使轻端的所有硬币--f[i]
顺带记录不等式的个数ineq,同时标记好硬币good[i]。
若ineq==0,则看!good[i]是否恰为1个。
若ineq>0,则!good[i]&&abs(f[i])==ineq的是嫌疑硬币
若恰有1个,则输出i;若没有或有多个则输出0.

/*32ms,192KB*/

const int mx = int(1e3) + 5;

int a[mx >> 1], b[mx >> 1], suspicion[mx]; /// 嫌疑程度
bool good[mx]; /// 正常硬币
char s[2];

inline int check(char op)
{
    return op == '<' ? -1 : op == '>';
}

int getans(int n, int ineq)
{
    int i, ans;
    bool ok = false;
    if (ineq == 0)
    {
        Forr(i, 1, n + 1) if (!good[i])
        {
            if (ok) return 0; /// 多个嫌疑硬币
            ans = i, ok = true;
        }
    }
    else
    {
        Forr(i, 1, n + 1) if (!good[i] && abs(suspicion[i]) == ineq)
        {
            if (ok) return 0; /// 多个嫌疑硬币
            ans = i, ok = true;
        }
    }
    return ok ? ans : 0;
}

int main()
{
    int n, k, m, i, add, ineq = 0;
    SII(n, k);
    while (k--)
    {
        SI(m);
        SA(a, i, m);
        SA(b, i, m);
        SS(s);
        add = check(s[0]);
        if (add)
        {
            For(i, m) suspicion[a[i]] += add, suspicion[b[i]] -= add; /// 累加嫌疑程度
            ++ineq;
        }
        else For(i, m) good[a[i]] = good[b[i]] = true; /// 正常硬币
    }
    PI(getans(n, ineq));
    return 0;
}

Comments

comments powered by Disqus