C. Binary String(思维+贪心)_资讯

C. Binary String(思维+贪心)

创始人

2024-02-12 07:37:06

0次

Problem - 1680C - Codeforces

给你一个由字符0和/或1组成的字符串s。

你必须从字符串的开头去除几个（可能是零）字符，然后从字符串的结尾去除几个（可能是零）字符。移除后，字符串可能会变成空的。删除的代价是以下两个值的最大值。

字符串中剩下的0个字符数。
从字符串中删除的字符数1。
你能达到的最小移除成本是多少？

输入
第一行包含一个整数t（1≤t≤104）--测试案例的数量。

每个测试用例由一行包含字符串s(1≤|s|≤2⋅105)，由字符0和/或1组成。

所有测试用例中的字符串s的总长度不超过2⋅105。

输出
对于每个测试案例，打印一个整数--你能达到的最小清除成本。

例子
inputCopy
5
101110110
1001001001001
0000111111
00000
1111
outputCopy
1
3
0
0
0
备注
考虑一下这个例子的测试案例。

在第一个测试案例中，有可能从开头删除两个字符，从结尾删除一个字符。只有一个1被删除，只剩下一个0，所以成本是1。
在第二个测试案例中，有可能从开头删除三个字符，从结尾删除六个字符。留下两个0字符，删除三个1字符，所以成本是3。
在第三个测试案例中，从开头删除四个字符是最理想的。
在第四个测试案例中，删除整个字符串是最佳选择。
在第五个测试案例中，保持字符串的原样是最佳选择。

题解:
设

t1 为任意字段中1的数目

t0 为任意字段中0的数目

设s1为整个字符串中1的数目

设t为任意字段的长度

res = max(t0,s1 - t1) = max(t0 +t1,s1) - t1 = max(t,s1) - t1(是不是很神奇,我也这么觉得QAQ)

如果t <= s1 要想结果最小,t1 应该最大,什么情况下t1最大,t == s1的时候,

res = s1(t) - t1

如果t >= s1,结果为t - t1 = t0,要想t0,尽可能小,t应该尽可能小,所以t == s1的时候

res = s1(t) - t1

所以结论就很明显了,结果应该为长度为s1的段的0的数目最小值

(直接根据题目推公式也是一种很好思路)

#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define int long long
//1 1 3 3 3
int n,ans;
int a[200050];
char s[200050];
void solve()
{cin >> s+1;int n = strlen(s+1);int cnt = 0;for(int i = 1;i <= n;i++){a[i] = a[i-1] + (s[i] == '0');if(s[i] == '1')cnt++;}int res = cnt;for(int i = cnt;i <= n;i++)res = min(res,a[i] - a[i-cnt]);cout<> t;while(t--){solve();}
}
//2 5
//3
//9 7 //2  3 4 3
//1 2 3 4 5
//      3

上一篇：java迷宫寻找最短路径

下一篇：袁佳怡献b门（袁佳怡结婚）袁佳怡献b门袁佳怡杨非同

C. Binary String(思维+贪心)

相关内容

热门资讯