codeforce每日一题汇总链接

题目链接
题目分数：2400

题目描述

输入$n(1≤n≤1e5)$和长为$n$的数组$a(1≤a[i]≤n)$。定义$f(k)$为最小的$m$，使得存在一种将$a$划分成$m$段的方式，其中每段的不同数字个数都不超过$k$。输出$f(1),f(2),… ,f(n)$。

样例

输入样例1

5
1 3 4 3 3

输出样例1

4 2 1 1 1 

输入样例2

8
1 5 7 8 1 7 6 1

输出样例2

8 4 3 2 1 1 1 1 

算法

(分治) $O(n\sqrt{n})$

我们可以体用分治的思想，将大问题化成小问题，所以我们可以将大的填好后，再填小的。
在这道题目中，我们设当前枚举到的区间是$[l,r]$，这个区间的意思是我们要算$l<=k<=r$，那我们可以先计算$f(l)，f(r)$，如果两者相等的话，那么$f(l)$到$f(r)$都相等，因为$f$是一个不增序列（下面证）。如果不相等的话，就去计算$[l+1,(l+r)>>1]，[(l+r)>>1+1, r-1]$。
假设$f$中$f[i]>f[j]$$(i>j)$，因为满足$j$的限制就一定满足$i$的限制，所以$f[i]$不会大于$f[j]$，最大也是跟$f[j]$相等。

C++ 代码

#include<bits/stdc++.h>

#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;
int w[N], res[N];
LL st[N], cnt;

int work(int x)
{
    cnt++;
    int tmp = 0, res = 0;
    for(int i=1;i<=n;i++){
        if(st[w[i]]==cnt) continue;
        if(!tmp) cnt ++, tmp = x, res ++;
        tmp --;
        st[w[i]] = cnt;
    }
    return res;
}

void solve(int l, int r)
{
    if(l>r) return;
    int r1 = work(l), r2 = work(r);
    res[l] = r1, res[r] = r2;
    if(r1==r2){
        for(int i=l;i<=r;i++) res[i] = r1;
        return;
    }
    int mid = l + r >> 1;
    solve(l + 1, mid), solve(mid + 1, r - 1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];

    solve(1, n);

    for(int i=1;i<=n;i++) cout<<res[i]<<" ";

    return 0;
}