蓝桥杯备考冲刺必刷题(C++) | 2928 分糖果-文章教程-杰人编程网

学习C++从娃娃抓起！记录下蓝桥杯备考比赛学习过程中的题目，记录每一个瞬间。

【题目描述】

最近暑期特训算法班的同学们表现出色，他们的老师肖恩决定给他们分发糖果。肖恩购买了$n$个不同种类的糖果，用小写的阿拉伯字母表示。每个糖果必须分发给一个同学，并且每个同学至少要分到一个糖果。同学们的开心程度定义为他们所分到的糖果组成的字符串$s[i]$的字典序。肖恩希望同学们的开心程度相差尽量小，因此他要找到一种方案，使得所有糖果组成的字符串中字典序最大的字符串尽可能小。请输出能够实现字典序最小可能的

$max(s[1],s[2],s[3],\dots,s[x])$ 。

【输入】

第一行输入两个整数$n$和$x$，分别表示有$n$个糖果$x$个同学。

第二行输入一个长度为$n$的字符串$S$， $S[i]$表示第$i$个糖果的种类。

数据保证$1\le n\le 10^6,1\le x\le n,S[i]\in ['a','z']$。

【输出】

输出一个字符串，为所有糖果组成的字符串中字典序最大的字符串最小的可能值。

【输入样例】

6 2
caabdc

【输出样例】

abccd

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, x;
char a[1000005];
int main()
{
    cin >> n >> x;  // 输入n和x
    for (int i=0; i<n; i++) {  // 输入a
        cin >> a[i];
    }
    sort(a, a+n);  //按照从小到大排序
    if (a[0]==a[n-1]) {  // 如果所有种类都一样，则将n个糖果平分给每个人
        if (n%x==0) {  // 如果可以整除
            for (int i=1; i<=n/x; i++) {
                cout << a[0];  // 平均分
            }
        } else {  // 如果不可以整除
            for (int i=1; i<=n/x+1; i++) {  // 需要平均分之后再加1
                cout << a[0];
            }
        }
    } else {  // 如果有两种及以上的糖果
        if (a[0]==a[x-1]) {  // 如果前x个是同一种，则每人分一样的
            if (a[x]==a[n-1]) {  // 如果后面的糖果也都一样，则平均分
                if ((n-x)%x==0) {  // 如果可以整除，则平均分
                    cout << a[0];
                    for (int i=1; i<=(n-x)/x; i++) {
                        cout << a[x];
                    }
                } else {  // 否则平均分之后再加1
                    cout << a[0];
                    for (int i=1; i<=(n-x)/x+1; i++) {
                        cout << a[x];
                    }
                }
            } else {  // 如果后面的糖果不是同一种
                for (int i=x-1; i<=n-1; i++) {  // 则将后面n-x个糖果都分给后面这个人（也可以说任一人）
                    cout << a[i];
                }
            }
        } else {  // 如果前x个不是同一种，则输出a[x-1]
            cout << a[x-1];
        }
    }
    return 0;
}

【运行结果】

6 2
caabdc
abccd