CodeCraft-22 and Codeforces Round #795 (Div. 2) C. Sum of Substrings

Problem - C - Codeforces

题意：

给一个二进制的字符串，f(x)函数表示将这个字符串每相邻的两位看做十进制（允许前导零）相加的值。每次操作可以交换相邻两位，问最多k次可以得到f(x)的最小值是多少。

思路：

贪心题，首先去考虑一个对象对答案的贡献是多少，然后去极端化地（即不考虑其他条件）使得贡献最大（或最小），最后再去考虑恰好满足限定条件

在此题中，我们去考虑1对函数值的贡献，在除去第一个字符和最后一个字符的1的所有位置中，1对答案的贡献都是11（1作为个位和作为十位），而第一个位置1的贡献是10，最后一个位置1的贡献是1

考虑完贡献之后，我们想使得贡献最小，极端化地考虑，就是把离最后一个位置最近的1移到最后一个位置（这里也有一个小小的贪心，就是我们要尽可能地减少操作次数，它操作次数有限制），然后把离第一个位置最近的1移到第一个位置，然后去模拟这个过程就好了，在模拟的过程中去维护中间1的个数，和移动的1对答案贡献的变化

Code：

#include <bits/stdc++.h>
using namespace std;
string s;
int n,k,L,R,cnt=0,res1=0,res2=0;
void solve(){
    cnt=0;res1=0;res2=0;
    s.clear();
    cin>>n>>k;
    cin>>s;
    s=" "+s;
    for(int i=1;i<=n;i++){
        if(s[i]=='1') cnt++;
    }
    for(int i=1;i<=n;i++){
        if(s[i]=='1'){
            L=i;
            break;
        }
    }
    for(int i=n;i>=1;i--){
        if(s[i]=='1'){
            R=i;
            break;
        }
    }
    if(cnt&&k>=n-R){
        k-=(n-R);
        cnt--;
        res1+=1;
    }
    if(cnt&&(k>=L-1)){
        k-=(L-1);
        cnt--;
        res2+=10;
    }
    cout<<cnt*11+res1+res2<<'\n';
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}

总结：

1、对于贪心题，首先去考虑一个对象对答案的贡献是多少，然后去极端化地（即不考虑其他条件）使得贡献最大（或最小），最后再去考虑恰好满足限定条件