[CF803D] Magazine Ad（二分，贪心）

你的名字 2021-01-08 13:35 454阅读 0赞

题意：字符串希望拆分成不大于k段，问如何拆分，使得每一行的字符串最短。其中有两个条件：空格或者连字符“-”允许换行。

二分每行最短的长度，检查的时候扫描i的字符串，固定两头，从右往左扫直到能换行，这样找到的是最长的满足每行长度<=二分到的值的长度。

#include <bits/stdc++.h>
      using namespace std;
      
      typedef long long LL;
      const int maxn = 1100100;
      int n, k;
      char s[maxn];
      
      bool ok(int p) {
         int ret = 0;
         for(int i = 0; i < n; ) {
             ret++;
             int r = i + p;
             if(r >= n) break;
             while(r > i && s[r-1] != ' ' && s[r-1] != '-') r--;
             if(r == i) return 0;
             i = r;
         }
         return ret <= k;
     }

int main() {
         // freopen("in", "r", stdin);
         // freopen("out", "w", stdout);
         while(~scanf("%d",&k)) {
             getchar();
             gets(s);
             n = strlen(s);
             int ret = 0;
             int l = 0, r = n;
             while(l <= r) {
                 int mid = (l + r) >> 1;
                 if(ok(mid)) {
                     r = mid - 1;
                     ret = mid;
                 }
                 else l = mid + 1;
             }
             printf("%d\n", ret);
         }
         return 0;
     }

发表评论取消回复

表情：

评论列表（有 0 条评论，454人围观）

还没有评论，来说两句吧...

相关阅读

相关【贪心+二分】CF1791G2

[Problem - 1791G2 - Codeforces][] 题意： ![1207a1f598e74fa39c4b7b9aff9f9e40.png][] ![19d

柔光的暖阳◎/ 2024年03月23日 23:39/ 0 赞/ 71 阅读

相关【贪心】CF1841 D

[Codeforces][] 题意： ![f231a62f84944973acc878c8bcd43a09.png][] ![eed5aa21f67e4bf8a27aad

绝地灬酷狼/ 2024年03月23日 23:24/ 0 赞/ 55 阅读

相关【贪心】CF1779 D

不会1700 [Problem - 1779D - Codeforces][] 题意： ![2812e830d8fc42acaa190aa13f186e7a.png][]

r囧r小猫/ 2024年03月23日 23:20/ 0 赞/ 87 阅读

相关【枚举gcd】CF803 C

[Problem - C - Codeforces][] 题意： ![c0f74c9a05f2451ead3cf4587dd84218.png][] 思路：要使所有数

落日映苍穹つ/ 2024年03月23日 22:42/ 0 赞/ 63 阅读

相关【二分答案】CF803 D

感觉之前的\1900好简单 [Problem - D - Codeforces][] 题意： ![47e9ce79fee54c63a55acba3cac6e937.pn

客官°小女子只卖身不卖艺/ 2024年03月23日 22:41/ 0 赞/ 48 阅读

相关【二分+贪心】CF1622 C

[Problem - 1622C - Codeforces][] 题意： ![f6cd9c72cb09404e95da429847de7fb5.png][] ![fdc7

古城微笑少年丶/ 2024年03月23日 21:59/ 0 赞/ 72 阅读

相关【二分+贪心】CF1665 C

[Problem - C - Codeforces][] 题意： ![acbe9c1d054143bb8090042f525333b9.png][] ![557b7c06

比眉伴天荒/ 2024年03月23日 21:45/ 0 赞/ 28 阅读

相关思维+贪心——cf1042D

/ 首先考虑从后往前计算lis，显然0的在很多情况下的贡献要大于1 如果遇上0，那么lis++，如果遇上1，那么cnt1++，并且用cnt1更新lis

一时失言乱红尘/ 2023年10月11日 09:09/ 0 赞/ 17 阅读

相关「CF803C」 Maximal GCD

题目链接 [戳我][Link 1] \\(Solution\\) 令\\(gcd\\)为\\(x\\),那么我们将整个序列\\(/x\\),则序列的和就变成了\\

比眉伴天荒/ 2023年08月17日 17:24/ 0 赞/ 121 阅读

相关 [CF803D] Magazine Ad（二分，贪心）

题意：字符串希望拆分成不大于k段，问如何拆分，使得每一行的字符串最短。其中有两个条件：空格或者连字符

你的名字/ 2021年01月08日 13:35/ 0 赞/ 455 阅读