A22071. 宝石项链
填空题
困难
知识点
题目描述
宝石项链
题目描述
小 A 有一串包含 n 枚宝石的宝石项链，这些宝石按照在项链中的顺序依次以 1,2,…,n 编号，第 n 枚宝石与第 1 枚宝石相邻。项链由 m 种宝石组成，其中第 i 枚宝石种类为 ti。
小 A 想将宝石项链分给他的好朋友们。具体而言，小 A 会将项链划分为若干连续段，并且需要保证每段都包含全部 m 种宝石。请帮小 A 计算在满足条件的前提下，宝石项链最多可以划分为多少段。
输入格式
第一行，两个正整数 n, m，分别表示宝石项链中的宝石的数量和种类数。
第二行，n 个正整数 t1,t2,…,tn，表示每枚宝石的种类。
输出格式
输出一行，一个整数，表示宝石项链最多可以划分为多少段。
样例
输入样例 1
6 2
1 2 1 2 1 2输出样例 1
3输入样例 2
7 3
3 1 3 1 2 1 2输出样例 2
2数据范围
对于40的测试点，保证2≤n≤1000。
对于所有测试点，保证2≤n≤105，2≤m≤n，1≤ti≤m，保证1,2....,m均在 t1,t2,…,tn中出现。
参考答案
#include<cstdio>
#include<algorithm>
using namespace std;
const int L = 20;
const int N = 2e5 + 5;
const int oo = 1e9;
int n, m;
int t[N], m[N]; // 注意原始代码里有int t[N], m[N]; 这里m和前面的m变量重名，保留原始
int cnt[N], jump[L][N];
int ans, tot;
int go(int u) {
int cnt = 0, ans = 0;
for (int i = L - 1; i >= 0; i--)
if (cnt + jump[i][u] <= n) {
cnt += jump[i][u];
ans += 1 << i;
u = (u + jump[i][u] - 1) % n + 1;
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &t[i]);
t[i + n] = t[i];
}
for (int i = 1, r = 0; i <= n; i++) {
while (tot < m) {
r++;
if (!cnt[t[r]]++)
tot++;
}
jump[0][i] = r - i + 1;
if (!--cnt[t[i]])
tot--;
}
for (int i = 1; i < L; i++) {
for (int j = 1; j <= n; j++) {
int tar = (j + jump[i - 1][j] - 1) % n + 1;
jump[i][j] = min(jump[i - 1][j] + jump[i - 1][tar], oo);
}
}
for (int i = 1; i <= n; i++)
ans = max(ans, go(i));
printf("%d\n", ans);
return 0;
}
上一题
下一题