题解 CF1408B 【Arrays Sum】

· · 题解

记 cnt = a 序列中不同的数的个数。

不难发现如果确定了 m ， 那么 cnt \leq m * (k-1) + 1 的数列都能被表示出来。

至于证明，考虑一下差分数组即可。

每一个 b_i 都可以使差分数组上的 k-1 个位置有值，那么就可以表示出有不超过 m * (k-1) + 1 个不同数字的 a_i 了。

最后特判一下 -1 即可。

\Theta(n)

code : 

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &x){
    static char ch; x = 0,ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }
int a[1000],n,k;
inline void solve(){
    int i,tot = 0;
    read(n),read(k);
    for (i = 1; i <= n; ++i) read(a[i]),tot += (i==1 || a[i] != a[i-1]);
    if (tot <= k){ cout << 1 << '\n'; return; }
    if (k == 1){ cout << -1 << '\n'; return; }
    int cnt = 1; tot -= k;
    while (tot > 0) tot -= k-1,++cnt;
    cout << cnt << '\n';
}
int main(){ int T; read(T); while (T--) solve(); return 0; }