博客

题目

如果一个字符串 S 恰好可以由某个字符串重复 K 次得到，我们就称 S 是 K 次重复字符串。例如 abcabcabc 可以看作是 abc 重复 3 次得到，所以 abcabcabc 是 3 次重复字符串。

同理 aaaaaa 既是 2 次重复字符串、又是 3 次重复字符串和 6次重复字符串。

现在给定一个字符串 S，请你计算最少要修改其中几个字符，可以使 S 变为一个 K 次字符串？

输入

输入第一行包含一个整数 K。

第二行包含一个只含小写字母的字符串 S。

其中，1 ≤ K ≤ 10^5, 1 ≤ |S| ≤ 10^5。其中∣S∣ 表示 S 的 长度。

输出

输出一个整数代表答案。如果 S 无法修改成 K 次重复字符串，输出 −1。

样例输入

2

aabbaa

样例输出

2

解题思路

如果分段数不是字符长度的因数，那么无法分割，输出-1；如果可以分割，则统计每一段对应位置上的字母，将其余字母修改为出现次数最多的字母方可保证修改次数最小。

代码

91分代码，最后一个测试点通不过。（但自认思路没错，看大佬题解据说测试用例有误，测试用例把截断的也视为可以修改了）

可见

题目 2600: 重复字符串最后一个测试用例

。

#include<stdio.h>
#include<string.h>
int n;//分为多少组

int same(char a[], int lena){
    int i,j,b[26],MAX,sum,r = 0;
    int g = lena/n;//每一组的长度
    for (i=0;i<g;i++)
    {
        MAX = 0;
        sum = 0;
        for (j=0;j<26;j++)
            b[j] = 0;//统计各个字母出现次数的hash散列
        for (j=i;j<lena;j+=g)
            b[a[j]-97]++;
        for (j=0;j<26;j++)//把其他字母变为字幕最多的那一个
        {
            if (b[j]>MAX)
                MAX = b[j];
            sum+=b[j];
        }
        r+=(sum-MAX);
    }
    return r;
}

int main()
{
	char a[100001];//只含小写字母的字符串
	scanf("%d\n%s",&n,a);
	int lena = strlen(a);
	if (lena%n!=0)
	    printf("-1");
	else
	    printf("%d",same(a,lena));
	return 0;
}