P14082 题解

引言

标签：数学贪心

正文

题目给出一个长度为

n

的字符串

s

要求切

k

刀将其分为

k+1

段连续非空子串

若分不出

k+1

段，则代表你无法分割

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

大致思路：

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

即价值的取值区间

如何求价值区间

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

初始价值可以这么计算：

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

例如样例中的

s

:aaabbc

可以找到

分界点 $1$ $\quad$ $a与b$ 的分界
分界点 $2$ $\quad$ $b与c$ 的分界

即有

3

个不同字母的串，价值为

3

可以用

for

循环实现

若第 $i$ 刀切在分界点上，那么总价值不增加
若第 $i$ 刀切在非分界点上，那么总价值 $+1$

初步计算

最小值取值=初始价值

+

切完

k

刀后增长的最小价值

最大值取值=初始价值

+

切完

k

刀后增长的最大价值

总共的价值数量

=

最大值

-

最小值

+1

即总共的价值数量

=

切完

k

刀后增长的最大价值-切完

k

刀后增长的最小价值

计算切完

k

刀后增长的最大价值

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

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

计算切完

k

刀后增长的最小价值

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

计算得最小价值=

max(

刀数-分界点数

,0)

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

代码实现

CPP

#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;
}

无注释版

CPP

#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;
}

文章操作

引言

正文

大致思路：

如何求价值区间

初步计算

代码实现

无注释版

相关推荐

评论

P14082 题解