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;
}
太强了
🥰