侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【模拟】重复字符串【蓝桥杯】

GabrielxD
2023-02-05 / 0 评论 / 0 点赞 / 197 阅读 / 589 字
温馨提示:
本文最后更新于 2023-02-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

重复字符串 - 蓝桥云课


问题描述

如果一个字符串 SS 恰好可以由某个字符串重复 KK 次得到,我们就称 SSKK 次重复字符串。例如 abcabcabc 可以看作是 abc 重复 33 次得到,所以 abcabcabc33 次重复字符串。

同理 aaaaaa 既是 22 次重复字符串、又是 33 次重复字符串和 66 次重复字符串。

现在给定一个字符串 SS,请你计算最少要修改其中几个字符,可以使 SS 变为一个 KK 次字符串?

输入格式

输入第一行包含一个整数 KK

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

其中,1K105,1S1051 \le K \le 10^5, 1 \le |S| \le 10^5。其中 S|S| 表示 SS 的 长度。

输出格式

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

样例输入

2
aabbaa

样例输出

2

运行限制

  • 最大运行时间:1s
  • 最大运行内存:128M

解题

方法一:模拟

思路

首先判断 SS 的长度是否是 KK 的整数倍,如果不是的话 SS 肯定无法修改成 KK 次重复字符串,输出 1−1

SS 分成长度为 SK\frac{S}{K}KK 段,然后枚举每一段的第 ii 个字符,统计出在该位置出现次数最多的字符出现的次数 mxmx,那么 kmxk-mx 就是该位置要修改的字符数量,把所有位置要修改的字符数量累和起来就得到了答案。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        in.nextToken();
        int k = (int) in.nval;
        char[] s = br.readLine().toCharArray();
        int n = s.length;
        if (n % k != 0) {
            System.out.println(-1);
            return;
        }
        int partLen = n / k;
        int[] cnts = new int[26];
        int ans = 0;
        for (int i = 0; i < partLen; ++i) {
            int mx = 0;
            Arrays.fill(cnts, 0);
            for (int j = i; j < n; j += (partLen)) {
                if (++cnts[s[j] - 'a'] >= mx) mx = cnts[s[j]- 'a'];
            } 
            ans += k - mx;
        }
        System.out.println(ans);
    }
}
0

评论区