问题本质

播放指针初始位置为已播放歌词个数 k0 = count(t[i] == '1')。未播放的歌词就是 s[k0+1..n]。幸运串长度为

m = Σ(cnt[i])  i=1..26

要让未播放部分正好是幸运串，必须满足

n − k = m   ⇔   k = n − m

因此，唯一可行的目标前缀长度 k* = n−m。每次操作将 k ±1，最少操作次数即为

| k0 − k* |

算法思路

1. 读入 cnt[1..26] 并计算 m = Σ cnt[i]。
2. 读入 n, s, t，统计 t 中 1 的个数 k0。
3. 目标前缀长度 k* = n − m。
4. 答案为 abs(k0 − k*)。

此处用到的主要操作是数组求和和字符串统计，时间复杂度为 O(n + 26)，空间复杂度为 O(n)。

复杂度分析

• 时间复杂度

  • 统计 cnt：O(26)
  • 读取并统计 t 中的 1：O(n)
  • 其他常数级操作
    总计：O(n)

• 空间复杂度

  • 存储 s 和 t：O(n)
  • 存储 cnt 和若干标量：O(1)
    总计：O(n)

代码实现

Python

def main():
    cnt = list(map(int, input().split()))
    m = sum(cnt)
    n = int(input())
    s = input()
    t = input()

    k0 = t.count('1')
    kt = n - m
    print(abs(k0 - kt))

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int[] cnt = new int[26];
        int m = 0;
        for (int i = 0; i < 26; i++) {
            cnt[i] = Integer.parseInt(st.nextToken());
            m += cnt[i];
        }
        int n = Integer.parseInt(in.readLine());
        String s = in.readLine();
        String t = in.readLine();

        int k0 = 0;
        for (char c : t.toCharArray()) {
            if (c == '1') k0++;
            else break;  // 保证1都在前面
        }
        int kt = n - m;
        System.out.println(Math.abs(k0 - kt));
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> cnt(26);
    long long m = 0;
    for (int i = 0; i < 26; i++) {
        cin >> cnt[i];
        m += cnt[i];
    }
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;

    int k0 = 0;
    for (char c : t) {
        if (c == '1') k0++;
        else break;  // t 中所有1在前
    }
    int kt = n - m;
    cout << abs(k0 - kt) << "\n";

    return 0;
}

题目内容

小红正在听歌，屏幕上同时展示着歌词和对应的播放进度条。设:

• 字符串$s$表示歌曲的完整歌词，下标从$1$开始，且仅由小写字母构成;
• 字符串$t$表示歌词的播放进度条，下标从$1$开始，且仅由字符$0$和$1$组成,其中:
• 当$t_i=0$时，表示第$i$个歌词尚未播放;
• 当$t_i=1$时,表示第$i$个歌词已经播放。

小红每次可以操作快进或回退一个歌词(即将播放指针向右或向左移动一个位置)，数据初始时和操 作过程均保证已经播放的歌词是$s$的一个前缀(可为空串)。

她的目标是:以尽可能少的操作次数，使得字符串$s$中未播放状态的歌词是"幸运串"。

请你计算，为了达到该目标，至少需要多少次操作?(数据保证可以在有限次内完成操作目标)

【幸运串】每种字母出现的次数为指定的次数，可为空串，具体可查看输入描述。

输入描述

输入第一行包含$26$个整数，表示一个幸运串每种字母出现的次数， $cnt_1 ,cnt_2，·,cnt_{26}(0 ≦cnt_i≦n)$对应$a, b,...,z$的出现次数。

输入第二行一个整数$n(1 ≦n≤2×10^5)$，表示歌词的长度。

输入第三行包含一个字符串$s$，表示歌曲的完整歌词，仅由小写字母构成。

输入第四行包含一个字符串$t$，表示歌词的播放进度条，仅由字符$0$和$1$组成。保证字符串中全部的$1$都位于全部的$0$之前(符合常识逻辑)。

输出描述

输出一个整数，表示使得未播放歌词构成幸运串所需要的最少操作次数。

样例1

输入

1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8
acabccab
11111000

输出

1

说明

只需要快进一次，即向右移动一次，使得$a$和$b$未播放的歌词都剩余一次。

样例2

输入

1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8
acabccab
11111100

输出

0

说明

不用操作，此时$a$和$b$未播放的歌词都剩余一次。