首页 > 代码库 > COJ 1411 Longest Consecutive Ones
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 ;
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 #define ll long long 6 const int N = 100005; 7 char s[N]; 8 int k , pos[N] ; 9 ll sum[N];10 11 bool ok(int st , int len)12 {13 int la = st + len - 1;14 int m = (st + la) >> 1;15 ll ans = 0;16 ans += (ll)pos[m]*(m-st+1) - (sum[m] - sum[st-1])- (ll)(m-st+1)*(m-st)/2 ;17 ans += (sum[la] - sum[m-1]) - (ll)pos[m]*(la-m+1) - (ll)(la-m+1)*(la-m)/2 ;18 if(ans > k) return false;19 return true;20 }21 22 int main()23 {24 // freopen("a.in" , "r" , stdin);25 int T;26 scanf("%d" , &T);27 while(T--){28 scanf("%s%d" , s+1 , &k);29 int len = strlen(s+1) , t = 0;30 for(int i = 1 ; i<=len ; i++){31 if(s[i] == ‘1‘) pos[++t] = i;32 }33 for(int i = 1 ; i<=t ; i++)34 sum[i] = sum[i-1] + pos[i];35 int maxnLen = 1 , st = 1;36 while(st + maxnLen - 1 <= t){37 if(ok(st , maxnLen)){38 // cout<<"here: "<<t<<" "<<st<<" "<<maxnLen<<endl;39 maxnLen ++;40 }41 else st++;42 }43 printf("%d\n" , maxnLen-1);44 }45 return 0;46 }
COJ 1411 Longest Consecutive Ones
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。