P9508 题解

rainygame · 2023-08-10 12:27:43 · 题解

发现题解区里的都是 O(n) 的题解，那我只好放一个 O(n^2) 的题解了。毕竟 n \le 10^3 嘛。

其实就是贪心。对于每一个 i，如果对于任意 1 \le j < i，[j,i) 里出现次数最多的数都达到了 \lceil \dfrac{i-j+1}{2}\rceil，那么说明可以放一个之前都没有出现过的；否则只能放 [1,i) 里面出现次数最多的。

其实还可以优化的，但是不想优化了。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 1001

int n, maxn, flag, res, ind, ind2;
int a[MAXN], cnt[MAXN];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i(1); i<=n; ++i){
        for (int j(1); j<=i; ++j) cnt[j] = 0;
        maxn = flag = 0;
        for (int j(i-1); j>=1; --j){
            ++cnt[a[j]];
            if (maxn < cnt[a[j]]){
                maxn = cnt[a[j]];
                ind = a[j];
            }
            res = i-j+1;
            if (maxn < (res>>1)+(res&1)) flag = 1;
        }
        if (!flag) a[i] = ++ind2;
        else a[i] = ind;
        cout << a[i] << ' ';
    }

    return 0;
}