codeforce645C_尺取法-白红宇的个人博客

codeforce645C_尺取法

发布日期：2021-10-24 14:20:43 浏览次数：5 分类：技术文章

本文共 1188 字，大约阅读时间需要 3 分钟。

题目链接：

题意：n个房间，0表示空房间，1表示住了人。一个农夫带着k头牛来入住，牛也是要一头一间 = = 问下农夫离最远的牛最近的距离是多少

被自己误导了，答案并不是在最短的k+1个房间的情况下求的

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               11 #define INF 0x3f3f3f3f12 using namespace std;13 typedef long long LL;14 15 char s[100010];16 int main()17 {18 int n, k, i, j;19 scanf("%d %d", &n, &k);20 scanf("%s", (s + 1));21 int l, num = 0, len, ll, rr, len2;22 for(i = 1; i <= n; i++)23 if(s[i] == '0'){24 l = i;25 num = 1;26 break;27 }28 int res = INF;29 for(j = i + 1; j <= n; j++)30 {31 if(s[j] == '0')32 {33 num++;34 if(num == k + 1)35 {36 num--;37 int mid = (l + j) / 2;38 while(s[mid] != '0') mid++;39 rr = mid;40 mid = (l + j) / 2;41 while(s[mid] != '0') mid--; 42 ll = mid;43 len = max(ll - l, j - ll);44 len2 = max(rr - l, j - rr);45 len = min(len, len2);46 res = min(len, res);47 for(int l1 = l + 1; l1 <= n; l1++)48 if(s[l1] == '0'){49 l = l1;50 break;51 }52 }53 }54 }55 printf("%d\n", res);56 return 0;57 }

View Code

转载于:https://www.cnblogs.com/luomi/p/5708975.html

转载地址：https://blog.csdn.net/weixin_30791095/article/details/98002166 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：iOS-图片拉伸,最常用的图片拉伸操作总结（干货）

下一篇：ajax 标准写法

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章