COJ 1411 Longest Consecutive Ones

题目大意：

希望在 k 步之内，将尽可能多的1移到相邻的位置上

这里依靠前缀和解决问题

我们用pos[i]保存第i个1的位置，这里位置我以1开始

用sum[i]保存前 i 个1从 0 点移到当前位置所需的步数

每次进行判断能否将 st 号到 la 号的1移到相邻位置，我们要先清楚，为了使移动步数最少，我们需要固定中间的数保持它的位置不动，将两边的数向它靠拢

那么移动的步数就分为左右两侧

中间的数编号为 m = （st + la）>> 1

首先将左侧移到中间，将 m 也作为其中的一部分，我们先将这 (m-st+1)个数均移到 pos[m]的位置上，而原本已经移好了 sum[m] - sum[st-1]个位置

因为是相邻，所以要把都在pos[m]上的位置一个个左移，分别左移 0 ， 1 ， 2 。。。。到(m-st)

所以左半部分为 (ll)pos[m]*(m-st+1) - (sum[m] - sum[st-1])- (ll)(m-st+1)*(m-st)/2 ;

右半部分同样道理，但是这回是因为其本身所在位置更大，所以是

(sum[la] - sum[m-1]) - (ll)pos[m]*(la-m+1) - (ll)(la-m+1)*(la-m)/2 ;

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 using namespace std;

 #define ll long long

 const int  N = ;

 char s[N];

 int k , pos[N] ;

 ll sum[N];

 bool ok(int st , int len)

 {

     int la = st + len - ;

     int m = (st + la) >> ;

     ll ans = ;

     ans += (ll)pos[m]*(m-st+) - (sum[m] - sum[st-])- (ll)(m-st+)*(m-st)/ ;

     ans += (sum[la] - sum[m-]) - (ll)pos[m]*(la-m+) - (ll)(la-m+)*(la-m)/ ;

     if(ans > k) return false;

     return true;

 }

 int main()

 {

    // freopen("a.in" , "r" , stdin);

     int T;

     scanf("%d" , &T);

     while(T--){

         scanf("%s%d" , s+ , &k);

         int len = strlen(s+) , t = ;

         for(int i =  ; i<=len ; i++){

             if(s[i] == '') pos[++t] = i;

         }

         for(int i =  ; i<=t ; i++)

             sum[i] = sum[i-] + pos[i];

         int maxnLen =  , st = ;

         while(st + maxnLen -  <= t){

             if(ok(st , maxnLen)){

                // cout<<"here: "<<t<<" "<<st<<" "<<maxnLen<<endl;

                 maxnLen ++;

             }

             else st++;

         }

         printf("%d\n" , maxnLen-);

     }

     return ;

 }

巴特西

COJ 1411 Longest Consecutive Ones

最新文章

热门文章