P14082 题解

· · 题解

引言

标签：数学贪心

正文

题目传送门

题目给出一个长度为n的字符串s

要求切k刀将其分为k+1段连续非空子串

若分不出k+1段，则代表你无法分割

求最终可以有多少种可能的价值

大致思路：

直接求出价值的可能最低点和可能最高点

即价值的取值区间

如何求价值区间

可以把原本的字符串的价值先求出

初始价值可以这么计算：

价值=每个字母的分界处数量+1

例如样例中的s:aaabbc

可以找到

即有3个不同字母的串，价值为3

可以用for循环实现

初步计算

最小值取值=初始价值+切完k刀后增长的最小价值

最大值取值=初始价值+切完k刀后增长的最大价值

总共的价值数量=最大值-最小值+1

即总共的价值数量=切完k刀后增长的最大价值-切完k刀后增长的最小价值

计算切完k刀后增长的最大价值

则使尽量每一刀都切在非分界点上

计算得最大价值=刀数-(字符长-1-分界点数)

计算切完k刀后增长的最小价值

则使尽量每一刀都切在分界点上

计算得最小价值=max(刀数-分界点数,0)

到这就可以开始实现代码了

代码实现

#include <bits/stdc++.h>
using namespace std;
signed main(){
    int k,n;
    cin>>n>>k;
    if(k+1>n){
        cout <<0;
        return 0;
    }//若无法分为k+1份，输出0
    string s;
    cin>>s;
    char noww=s[0];//记录上一个字符
    int size_=s.size(),cs=1;//长度和初始价值
    for(int i=1;i<size_;i++){
        if(noww!=s[i]){
            cs++;
            noww=s[i];
        }
    }
    int fjd=cs-1;//分界点
    int more=max(k-fjd,0);
    int l=cs+more;
    int less=n-1-fjd,aaa=0;
    if(less<k)aaa=k-less;
    //若非分界点数小于刀数，统计最高上限的限制
    int r=cs+k-aaa;//最高-限制
    cout <<r-l+1;//统计区间
    return 0;
}

无注释版

#include <bits/stdc++.h>
using namespace std;
signed main(){
    int k,n;
    cin>>n>>k;
    if(k+1>n){
        cout <<0;
        return 0;
    }
    string s;
    cin>>s;
    char noww=s[0];
    int sz=s.size(),c=1;
    for(int i=1;i<sz;i++){
        if(noww!=s[i]){
            cs++;
            noww=s[i];
        }
    }
    int f=c-1;
    int more=max(k-f,0);
    int l=c+more;
    int ls=n-1-f,a=0;
    if(ls<k)a=k-ls;
    int r=c+k-a;
    cout <<r-l+1;
    return 0;
}