每日一道思维题——CF1691C - Sum of Substrings

标签：CF1691C 10 cnt int ed Sum Substrings ans 11

题意：

给定一个长度为n的字符串算由S_i S_i+1构成的子字符串值如00为0，01为1，10为10，11为11

F(s) 为所有值之和求出此值的最小值

思路：

优先将1放到最后，其次将1放在开头其余的位置，一个1ans+=11

代码：

#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int N = 2*1e5+10; char str[N]; int main() {     int t;     scanf("%d", &t);     while(t--)     {         int n, k, ans = 0, cnt = 0;         scanf("%d%d", &n, &k);         scanf("%s", str);         int be = -1, ed = -1;         for(int i = 0; i < n; i++)         {             if(str[i]=='1')             {                 if(be == -1) be = i;                 ed = i;                 cnt++;             }         }
        if(ed != -1 && k >= n-1-ed)         {             k -= (n-1-ed);             cnt--;             ans += 1;         }
        if(k >= be && cnt)         {             k -= be;             cnt--;             ans += 10;         }
        ans += (cnt*11);
        printf("%d\n", ans);     }     return 0; }

 

标签：CF1691C,10,cnt,int,ed,Sum,Substrings,ans,11
From： https://www.cnblogs.com/lys-blogs123/p/17092200.html