665 False coin

題目連結

題目翻譯

N 枚硬幣中有一枚是假幣，重量和其他不同（可能偏輕或偏重）。透過 K 次天平稱重的結果（< / > / =），找出哪一枚是假幣。如果無法唯一確定就輸出 0。

輸入

M 組測資（測資間空一行），每組第一行 N K，接下來 K 組稱重記錄：先讀一個數 P（每側硬幣數），再讀 P 個左盤硬幣編號和 P 個右盤硬幣編號，最後一行是結果符號。

輸出

每組輸出假幣編號（或 0），組間空一行。

解題思路

對每一枚硬幣 i（從 1 到 N），分別假設它偏輕（L）或偏重（H），驗證這個假設是否和所有 K 次稱重結果都一致。

驗證方式：用虛擬重量代替（L 假設：假幣重量=1，其餘=2；H 假設：假幣=2，其餘=1），計算左右盤的虛擬總重，再看是否符合 < / > / = 的結果。

把每次稱重的所有硬幣存在一個 vector（前半是左盤，後半是右盤），用指標位置 &k - j.fi.data() >= j.fi.size()/2 判斷是哪一盤。

如果恰好只有一枚硬幣在 L 或 H 假設下通過全部 K 次，就輸出它，否則輸出 0。

程式碼

//author: Piau
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>

signed main() { WA();
    int t; for (cin >> t; t--;) {
        int n, k; cin >> n >> k;
        vector<pair<vector<int>, char>> v(k);
        for (auto &i : v) {
            int siz; cin >> siz;
            i.fi.resize(siz*2);
            for (auto &j : i.fi) cin >> j;
            cin >> i.se;
        }

        int coin = 0, cnt = 0;
        for (int i = 1; i <= n; i++) {
            int passL = 0, passH = 0;
            for (auto &j : v) {
                int l[2] = {}, h[2] = {};
                for (auto &k : j.fi) {
                    l[&k-j.fi.data() >= j.fi.size()/2] += (k == i ? 1 : 2);
                    h[&k-j.fi.data() >= j.fi.size()/2] += (k == i ? 2 : 1);
                }
                passL += j.se == '<' && l[0] < l[1] || j.se == '>' && l[0] > l[1] || j.se == '=' && l[0] == l[1];
                passH += j.se == '<' && h[0] < h[1] || j.se == '>' && h[0] > h[1] || j.se == '=' && h[0] == h[1];
            }
            if (passL == k || passH == k) coin = i, cnt++;
        }

        if (cnt == 1) cout << coin << '\n';
        else cout << "0\n";
        if (t) cout << '\n';
    }
}