ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[CodeForces]1680 C. Binary String(双指针 + 贪心)

2022年5月14日 1076点热度 0人点赞 0条评论

题目传送门:Problem - C - Codeforces

题目大意

有多组测试用例。

给定一个01字符串S,从前往后删除若干字符,从后往前删除若干字符,留下中间连续的一串字符,不同的方案的代价为max(删除的1的个数,留下的0的个数),问最小的代价是多少?

思路(双指针 + 贪心)

会留下中间一段,所以可以用双指针来表示中间这一段,枚举左端点,然后贪心,复杂度为O(N)。

贪心的原理为:当留下的0和删除的1相等的时候,就不要再往右扩大了,因为再向右扩大留下区间范围的话,留下的0只会增加,删除的1只会减少,这样只会让代价更大。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 9, inf = 8e18;
char s[maxn];

void solve()
{
	cin >> s + 1;
	int N = strlen(s + 1);
	int removed_1 = 0, left_0 = 0, ans = inf;
	for(int i = 1;i <= N; ++ i)if(s[i] == '1')removed_1 ++;
	
	for(int i = 1, j = 0;i <= N; ++ i)
	{
		while(j < N && left_0 < removed_1)
		{
			++ j;
			if(s[j] == '0')left_0 ++;
			else removed_1 --;
			ans = min(ans, max(removed_1, left_0));
		}
		if(s[i] == '0')left_0 --;
		else removed_1 ++;
		ans = min(ans, max(left_0, removed_1));
	} 
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(0);
	int _;cin >> _;
	while(_ --)solve();
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ codeforces 双指针 算法竞赛 贪心
最后更新:2022年7月9日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 题目大意
  • 思路(双指针 + 贪心)
  • 代码

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号