题目链接: http://exercise.acmcoder.com/online/online_judge_ques?ques_id=3362&konwledgeId=40
解题思路: 正向求解很难. 考虑如果给定一个长度, 判断这个长度 x 是否符合要求是很简单的, 只需要贪心对于每个 1 划分一个长度 x 的段就可以了.
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- const int MAXN=100005;
- const LL MOD7 = 1e9+7;
- char s[MAXN];
- int n;
- int m;
- bool check(int x)
- {
- int i=0;
- int cnt=0;
- while (i<n)
- {
- while (i<n && s[i]=='0') ++i;
- if (i>=n) break;
- ++cnt;
- i+=x;
- }
- return cnt<=m;
- }
- void biSearch()
- {
- int l=1;
- int r=n;
- int mid;
- while(l<=r)
- {
- mid=(l+r)/2;
- // printf("l=%d r=%d mid=%d check(%d)=%d\n",l,r,mid, mid, check(mid));
- if (check(mid)) r=mid-1;
- else l=mid+1;
- }
- printf("%d\n", r+1);
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("test.txt","r",stdin);
- #endif // ONLINE_JUDGE
- int Case;
- scanf("%d",&Case);
- for (int t=1;t<=Case;++t)
- {
- scanf("%d%d",&n,&m);
- scanf("%s",s);
- printf("Case %d:", t);
- int flags=0;
- for (int i=0;s[i];++i)
- {
- if (s[i]=='1')
- {
- flags=1;
- break;
- }
- }
- if (!flags) printf("0\n");
- else biSearch();
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2587841.html