Codeforces 140C（二分、构造）

要点

• 可以贪心选数量最多的那三个构造
• 二分的话里面的check我不太会。正解是既然当前答案为\(k\)个，那每个物品最多只会出现\(k\)次，多余的丢掉，剩下的总数如果大于等于\(3k\)则true。最后输出答案时也是小小技巧吧，用\({1,1+k,1+2k}\)组成一组，因为多于\(k\)个的都删了所以这三个一定不同。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int maxn = 1e5 + 5;
int n, a[maxn];
vector<int> v, x;

bool ok(int mid) {
    int cnt = 1;
    x.clear();
    for (int i = 1; i <= n; i++) {
        if (a[i] == a[i - 1]) {
            cnt++;
            if (cnt <= mid) x.push_back(a[i]);
        } else {
            cnt = 1;
            x.push_back(a[i]);
        }
    }
    if (x.size() < 3 * mid) return false;
    return true;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
        scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);

    int l = 0, r = n / 3, ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (ok(mid)) {
            l = mid + 1;
            ans = mid;
            v = x;
        } else  r = mid - 1;
    }

    printf("%d\n", ans);
    for (int i = 0; i < ans; i++) {
        printf("%d %d %d\n", v[i + ans * 2], v[i + ans], v[i]);
    }
}

Codeforces 140C（二分、构造）

原文：https://www.cnblogs.com/AlphaWA/p/10895641.html