【cf】Round 128 C. Binary String

Topic link ：Problem - C - Codeforces

translate （ Reference resources ）：

t Group data , One string per group , You can delete a string from front to back and a string from back to front , The cost of deletion is max（ In the remaining string 0 The number of is recorded as num1, Deleted string 1 The number of is recorded as num2）, Find the minimum value of the cost .

  analysis ：

We consider prefixes and f[i] Record 0~i in 1 The number of .

remember len Is the remaining string length ,n1 Is in the remaining string 1 The number of ; The remaining string range  (i,i+len], be

num1=f[i]+(f[n]-f[i+len])=f[n]+f[i]-f[i+len]; 

num2=len-(f[i+len]-f[i])=len+f[i]-f[i+len];

cost=max(num1,num2)=max(f[n],len) - (f[i+len]-f[i]) = max(f[n],len) - n1;

len The bigger, the more len<=f[n] Within the scope of max(f[n],len) No effect , stay len>f[n] Within the scope of max(f[n],len) The bigger it is ;n1 The larger in any range . stay len<=f[n] Inside ,cost Decline ; stay len>f[n] Inside max(f[n],len) The higher the speed, the faster it will be n1 The rate of increase is fast , Why? ？ because max(f[n],len) The increased value is the length of the increased string , and n1 The increased value is in the increased string 1 The number of （ Because the added string has 1 Also have 0）. So in len be equal to f[n] The cost is the least Of .

cost-len The function image is roughly shown in the figure below ：

 

Prove the following ：

Remember that the remaining string is s1, The deleted string is s2, We have to make s1 Medium 0 As small as possible , send s2 Medium 1 As small as possible ,

cost=max(f[n]-n1,len-n1), We consider the len And f[n] The relationship between

Preface ：costa,costb,costc Are the costs under the corresponding circumstances ,n1a,n1b,n1c Are in the remaining string in the corresponding case 1 The number of ,len Is the remaining string length .

a） The remaining string s1 length len be equal to f[n]：

costa=num1a=num2a=f[n]-n1a;

b） The remaining string s1 length len Less than f[n]：

num1b=len-n1b;

num2b=f[n]-n1b;

costb=num2=f[n]-n1b

because a The remaining string length is greater than b The remaining string length , therefore n1a>=n1b

therefore costb>=costa,a Situation ratio b Better situation

c） The remaining string s1 length len Greater than f[n]：

num1c=len-n1c;

num2c=f[n]-n1c;

costc=len-n1c;

len>f[n],n1c>n1a;

n1c-n1a<=len-f[n] ---> len-f[n]-n1c+n1a>=0

costc-costa=(len-n1c)-(f[n]-n1a)=len-f[n] -n1c+n1a >=0;

therefore costc>=costa,a Situation ratio c Better situation

Sum up , stay a Optimal in case . Therefore, the enumeration length is f[n] Find the price of the string , For all lengths f[n] Minimize the cost of string .

See the code for details. ：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 50;
int f[N]; // Record 1 The number of prefixes and 
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        char s[N];
        cin >> s;
        int n;
        for (n = 0; s[n] != '\0'; n++)
            f[n + 1] = f[n] + int(s[n] == '1'); // The prefix and 
        int ans = f[n];                         // The remaining string size is 0
        for (int i = 0; i + f[n] <= n; i++)
            ans = min(ans, f[i] + f[n] - f[i + f[n]]);
        cout << ans << endl;
    }
}

 ending

Purring , It's so delicious , Standard program oriented problem solving , Maybe it's not very clear , What's wrong , Please dalao correct