C++(g++ 7.5.0) 解法, 执行用时: 237ms, 内存消耗: 8244K, 提交时间: 2022-10-03 10:14:23

#include <bits/stdc++.h>

using namespace std;
const int N=2000013;
int a[N];
void solve(){
    int n,m,k;cin>>n>>m>>k;int stp;
    for(int i=1;i<=n;i++)cin>>a[i],a[i+n]=a[i];
    for(int i=n+1;i>=1;i--)if(a[i]!=a[i-1]){
            stp=i;break;
    }
    int nw=0;int r=0;int mx=0;
    for(int i=stp;i<stp+n;i++){
        if(a[i]!=a[i-1])r+=(nw+k-1)/k,mx=max(nw,mx),nw=0;
        nw++;
    }
    r+=(nw+k-1)/k,mx=max(nw,mx),nw=0;
    if(mx<k)cout<<-1<<'\n';
    else cout<<r<<'\n';
}

int main(){
    ios::sync_with_stdio(0);
    int T;cin>>T;
    while(T--)solve();
}

Python3 解法, 执行用时: 2081ms, 内存消耗: 122424K, 提交时间: 2022-09-24 11:46:42

T = int(input())
while T > 0:
    T -= 1
    n, m, k = map(int, input().split())
    c = list(map(int, input().split()))
    i = 0
    cols = []
    while i < n:
        j = i
        while j < n and c[j] == c[i]:
            j += 1
        cols.append(j - i)
        i = j
    if cols[0] != n and c[0] == c[n - 1]:
        cols[0] += cols[-1]
        cols.pop()
    ans = 0
    flag = False
    for i in cols:
        if i >= k:
            flag = True
        ans += (i + k - 1) // k
    if not flag:
        ans = -1
    print(ans)

C++(clang++ 11.0.1) 解法, 执行用时: 385ms, 内存消耗: 4332K, 提交时间: 2022-09-25 10:19:19

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n,m,k,a[N];

int f()
{
	int Max = 0,ans = 0,num = 0;
	while(n>1 && a[n]==a[1]) n--,num++;
	
	num++;
	for(int i=2;i<=n;i++)
		if(a[i]==a[i-1]) num++;
		else ans += (num + k-1)/k,Max = max(Max,num),num = 1;
		
	ans += (num + k-1)/k,Max = max(Max,num),num = 1;
	
	if(Max>=k) return ans;
	return -1; 
}

int main()
{
	int t; scanf("%d",&t);
	while(t--)
	{
		cin >>n >>m >>k;
		for(int i=1;i<=n;i++) cin >>a[i];
		printf("%d\n",f());
	}
	return 0;
}