首页 > 代码库 > cogs 942. [東方S3] 比那名居天子
cogs 942. [東方S3] 比那名居天子
二次联通门 : cogs 942. [東方S3] 比那名居天子
/* cogs 942. [東方S3] 比那名居天子 二分水题 二分所求区间长度 判断后缩小范围即可 */ #include <cstring> #include <cstdio> #define Max 1000000 void read (int &now) { now = 0; register char word = getchar (); while (word < ‘0‘ || word > ‘9‘) word = getchar (); while (word >= ‘0‘ && word <= ‘9‘) { now = now * 10 + word - ‘0‘; word = getchar (); } } char line[Max]; int N, K; bool Judge (int key) { int Count = 0; for (register int i = 0; i < N; i ++) if (line[i] == ‘1‘) { i += key - 1; Count ++; if (Count > K) return false; } return true; } int main (int argc, char *argv[]) { freopen ("tenshi.in", "r", stdin); freopen ("tenshi.out", "w", stdout); read (N); read (K); scanf ("%s", line); int pos = 0; for (pos = 0; line[pos] == ‘0‘; pos ++); if (pos == N) { putchar (‘0‘); return 0; } register int Answer; for (register int l = 1, r = (N << 1), Mid; l <= r; ) { Mid = l + r >> 1; if (Judge (Mid)) { r = Mid - 1; Answer = Mid; } else l = Mid + 1; } printf ("%d", Answer); return 0; }
cogs 942. [東方S3] 比那名居天子
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。