AcWing 3807. 构造字符串

原题链接

题目描述

给定两个整数 $n$ 和 $k$ ，请你构造一个长度为 $n$ 的字符串 $s$ 。

字符串 $s$ 需满足：

$s$ 由前 $k$ 个小写字母构成，且前 $k$ 个小写字母均在 $s$ 中出现至少一次。
前 $k$ 个小写字母中，出现次数最少的字母的出现的次数尽可能多。

输出任意满足条件的字符串 $s$ 。

输入格式

第一行包含整数 $T$ ，表示共有 $T$ 组测试数据。

每组数据占一行，包含两个整数 $n$ 和 $k$ 。

输出格式

每组数据输出一个结果，表示满足条件的字符串 $s$ 。

如果答案不唯一，输出任意合理方案均可。

数据范围

$1≤T≤100$
$1≤n≤100$
$1≤k≤min(n,26)$

样例

输入样例:

输出样例：

cbcacab
abcd
baabab

思路

题目要求出现次数最小的字母，出现次数尽可能多，只要尽可能平均的分配字母即可。

题目至少需要 $k$ 个不同的字母。那么每个字母都可以出现 $n/k$ 次。

然后将剩下的 $n$ % $k$ 个位置，用前 $k$ 个字母中，不同的字母填入即可。

代码

C++

#include <iostream>

using namespace std;

int main()
{
    int T;
    cin >> T;
    while ( T-- )
    {
        int n, k;
        cin >> n >> k;
        string res;
        for ( int i = 0; i < n / k; i++ )
            for ( int j = 0; j < k; j++ )
                res += 'a' + j;

        for ( int i = 0; i < n % k; i++ )
            res += 'a' + i;
        cout << res << endl;
    }
    return 0;
}

Java

import java.util.*;

public class Main
{
    static Scanner in = new Scanner(System.in);
    
    public static void main(String args[])
    {
        int T = in.nextInt();
        while ( T-- > 0 ) 
        {
            int n = in.nextInt(), k = in.nextInt();
            StringBuilder res = new StringBuilder();
            for ( int i = 0; i < n / k; i ++ )
                for ( int j = 0; j < k; j ++ )
                    res.append((char) ('a' + j));
            for ( int i = 0; i < n % k; i ++ )
                res.append((char) ('a' + i));
            System.out.printf("%s\n", res.toString());
        }
    }
}