首页 > 代码库 > CSU 1411: Longest Consecutive Ones

CSU 1411: Longest Consecutive Ones

2024-07-02 04:26:43   226人阅读


关键是通过预处理,使每个区间内的1移动到一起的最少步骤可以在O(1)时间算出来....


1411: Longest Consecutive Ones

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 185  Solved: 40
[Submit][Status][Web Board]

Description

Given a string consists of 0 and 1, you can swap any two adjacent digits of it, but you can not swap more than K times. So, what is the maximum probable length of the longest consecutive ones you can get after your swapping?
For example, assume the string is 110101001011, if you swap 3 times like this:
110101001011 --> 110011001011 --> 110011010011 --> 110011100011
The length of the longest consecutive ones is 3: 110011100011.
But if you swap 3 times like this:
110101001011 --> 111001001011 --> 111010001011 --> 111100001011
The length of the longest consecutive ones is 4: 111100001011.

Input

The first line contains an integer T (T > 0), means there are T test cases.
For each test case, there is only one line with a string consists of 0 and 1 and an integer K (0 <= K <= 109). The length of that string is between 1 and 105 inclusive.

Output

For each test case, output the maximum probable length of the longest consecutive ones you can get after your swapping.

Sample Input

3
11101 0
110101001011 3
0000000 1000000000

Sample Output

3
4
0

HINT

Source

中南大学第八届大学生程序设计竞赛


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long int LL;
const int maxn=100100;

LL pos[maxn],sum[maxn],K;
int cnt;
char str[maxn];

bool ck(int l,int r)
{
    int mid=(l+r)/2;
    LL temp=0;
    int num=mid-l;
    temp+=pos[mid]*num-num*(num+1)/2-sum[mid-1]+sum[l-1];
    num=r-mid;
    temp+=sum[r]-sum[mid]-num*(num+1)/2-pos[mid]*num;
    if(temp>K)
        return false;
    return true;
}

int main()
{
    int T_T;
    scanf("%d",&T_T);
    while(T_T--)
    {
        scanf("%s",str+1);
        scanf("%I64d",&K);
        int len=strlen(str+1);
        cnt=1;
        for(int i=1;i<=len;i++)
        {
            if(str[i]==‘1‘)
            {
                pos[cnt]=i;
                sum[cnt]=pos[cnt]+sum[cnt-1];
                cnt++;
            }
        }
        cnt--;
        int i=1,ans=0,maxn=1;
        while(true)
        {
            int j=i+maxn-1;
            if(j>cnt) break;
            if(ck(i,j))
            {
               ans=maxn; maxn++;
            }
            else i++;
        }
        printf("%d\n",ans);
    }
    return 0;
}





联系
我们