CodeForces-327A-Flipping Game

题意:

给出一个01串,要求只能翻转一次区间(在翻转的区间内,0变成1,1变成0),问翻转后1的数量最大是多少。

 

思路:

如果全部都为0肯定全部翻转,如果全部为1肯定只翻转一次,所以默认max应该为-1而不是-inf;

算出一段区间内0和1的个数差值cnt,与后序数字进行比较,不断更新最大值maxx和cnt。

 

AC代码:

CodeForces-327A-Flipping Game
 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<list>
 7 #include<map>
 8 #include<stack>
 9 #include<stdlib.h>
10 #include<vector>
11 #define eps 1e-9
12 #define read(x) scanf("%d",&x)
13 #define mem(a,b) memset(a,b,sizeof(a))
14 #define PI acos(-1)
15 #define F(a,b,c) for (int a=b;a<=c;a++)
16 #define RF(a,b,c) for (int a=b;a>=c;a--)
17 #define sc(a) scanf("%d",&a)
18 #define SC(n,m) scanf("%d %d",&n,&m)
19 #define pr(a) printf("%d\n",a)
20 using namespace std;
21 #define inf 0x3f3f3f3f
22 typedef long long ll;
23 
24 int a[110];
25 
26 int main()
27 {
28     int n;
29     cin>>n;
30     int sum=0,cnt=0,maxx=-1;
31     F(i,1,n)
32     {
33         int x;
34         cin>>x;
35         if(x==0)
36         {
37             cnt++;
38             maxx=max(maxx,cnt);
39         }
40         else
41         {
42             cnt--;
43             if(cnt<0)
44                 cnt=0;
45         }
46         if(cnt<maxx||!cnt)
47             sum+=x;
48     }
49     cout<<sum+maxx<<endl;
50     return 0;
51 }
View Code

 

 

这个博客进行了时间上的优化:

https://www.cnblogs.com/mqxnongmin/p/10668455.html

上一篇:DDIA学习笔记6——chapter9:一致性与共识


下一篇:[leetcode] 861. Score After Flipping Matrix