利用分治法解决假硬币问题（C++）

以下是利用分治法解决假硬币问题的C++代码：

#include <iostream>
#include <vector>
using namespace std;

// 分治函数
int findFakeCoin(vector<int>& coins, int left, int right) {
    int len = right - left + 1;
    if (len == 1) return left;
    if (len == 2) return coins[left] < coins[right] ? left : right;
    int mid = (left + right) / 2;
    int leftSum = 0, rightSum = 0;
    for (int i = left; i <= mid; i++) leftSum += coins[i];
    for (int i = mid + 1; i <= right; i++) rightSum += coins[i];
    if (leftSum == rightSum) return -1;
    return leftSum < rightSum ? findFakeCoin(coins, left, mid) : findFakeCoin(coins, mid + 1, right);
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> coins(n, 1);
    for (int i = 0; i < k; i++) {
        int fake, l, r;
        cin >> fake >> l >> r;
        for (int j = l - 1; j < r; j++) coins[j] = fake;
    }
    int fakeIndex = findFakeCoin(coins, 0, n - 1);
    if (fakeIndex == -1) cout << "NO fake coin" << endl;
    else cout << "Fake coin index: " << fakeIndex << endl;
    return 0;
}

代码中，`findFakeCoin`函数是分治函数，从输入的硬币序列`coins`和左右边界`left`、`right`分别计算出左右两边的硬币总重量，进行比较，如果相等说明没有假币，返回-1；如果左重右轻，说明假币在左边，递归分治左半边；否则递归分治右半边。

在`main`函数中，首先根据输入，将假币对应位置的硬币重量设为假币重量，然后调用`findFakeCoin`函数查找假币位置。如果返回-1，说明没有假币，否则返回假币位置。

以上是分治法解决假硬币问题的C++代码。