题解：P11447 「ALFR Round 3」C 割

zhanghy123 · 2024-12-21 16:54:17 · 题解

思路

不难想到一个性质：字符串 S 的字典序最大的子序列，一定为以其最大字符首次出现的位置为起点的，单调不增序列。所以考虑到使用单调栈维护。显然，当 k=1 时，把整个字符串从头到尾维护一遍的结果就是答案。

现在要分成 k 段，可以先把几个最大字符的位置存出来。设有 cnt 个最大字符，一个容易想到的结论是，最佳的分割方式的分割点一定在这些最大字符之后紧邻的一个位置。因为每个最大字符，都一定会成为它所在小段 s 的最大字典序子序列 f(s) 的一部分。在其之后紧邻的一个位置分割，就保证了 f(s) 最后一位也是最大字符，没有了后面的冗余字符来使其字典序增大。这样，f(s) 就仅由最大字符构成。

那么，问题就转化为将 cnt 个最大字符放入 k 个序列中。要求最小的分割方式权值，就要使最大字符最多的序列中最大字符的数量尽量少。换句话说，最佳的分配方式是按抽屉原理，平均地分配最大字符。这时还需要分类：

• 当 cnt 不能被 k 整除时，最大字符最多的区间 s 的 f(s) 就有 \lceil\frac{cnt}{k}\rceil 个字符。此时我们可以将该区间放在前面，最终答案就是 \lceil\frac{cnt}{k}\rceil 个最大字符；
• 当能整除时，因为需要平均分配，所以这整个字符串最后一个最大字符的末尾就没有分割点。此时，最后一个最大字符后面还有冗余字符，需要再跑一遍单调栈，把这些冗余字符组成的串的最大字典序子序列拼接在 \frac{cnt}{k} 个最大字符之后。

总结：最终答案为 \lceil\frac{cnt}{k}\rceil 个最大字符。若能整除，则再跑一遍单调栈，把尾巴的最大字典序子序列拼接在后面。

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,pos[200001],cnt,top;
string s,ans1,ans2;
char maxx,stk[200001];
void ddz(int begin)//单调栈求以 begin 为起点的最大字典序子序列 
{
    for(int i=begin; i<n; i++)
    {
        while(top && stk[top]<s[i]){top--;}
        stk[++top]=s[i];
    }
    for(int i=1; i<=top; i++)
        cout<<stk[i];
}
int main()
{
    cin>>n>>k>>s; 
    for(int i=0; i<n; i++)
        maxx=max(s[i],maxx);
    for(int i=0; i<n; i++)
        if(s[i]==maxx) pos[++cnt]=i;
    if(k==1){
        ddz(0);
        return 0;
    }
    for(int i=1; i<=ceil(cnt*1.0/k); i++)
        cout<<maxx;
    if(cnt%k==0)//能整分，最后一段需要再求一次 
        ddz(pos[cnt]+1);
    return 0;
}