CF803D Magazine Ad 题解

Echoternity · 2022-04-27 16:45:03 · 题解

随机跳了一道题，就放在题库里，原以为是一道 dp，结果是到二分。

首先，我们必须要做的就是将难以处理的字符串转化为我们比较熟悉的数字，因为在所有的 - 和 ' '之间都可以断，所以我们将其中的字符串转化为一个数记为该段的长度。最后我们会得到一个长度为 n 的数组 val[i] ，而我们要将这 n 个数分成 k 段。

到这里，这道题就显然了。

将 n 个数分成 k 个区间，使最大区间和最小

我们直接二分区间长度，然后暴力该区间和满足需要多少段。

check(int len) 函数：

inline bool check(int x)
{
    int res=0,cnt=0;
    for(int i=1;i<=tot;++i)
    {
        if(val[i]>x) return 0;
        if(res+val[i]<=x) res+=val[i];
        else ++cnt,res=val[i];
    }
    // printf("%d %d\n",x,cnt); //调试用
    if(cnt>=k) return 0;
    return 1;
}

记得特判 val[i]>x 的情况（即单个区间的长度已经大于了需要判定的长度）

然后这道题就十分简单了。

有几个注意的点：

• 对于每一个区间，其末尾的 - 和空格也算该区间的一部分

• 对于整行字符串的输入，因为 gets() 函数的废除，建议用 while(getchar()) 直接输入，不要使用 stl 库。