Leetcode-995 Minimum Number of K Consecutive Bit Flips(K 连续位的最小翻转次数)

 1 #define maxn 30002
 2 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
 3 int dir[maxn],f[maxn],n;
 4 class Solution
 5 {
 6     public:
 7         int solve(int k)
 8         {
 9             memset(f,0,sizeof(f));
10             int sum=0,res=0;
11             for(int i=0; i+k<=n; i++)
12             {
13                 if((dir[i] + sum) %2== 1)
14                 {
15                     f[i]=1;
16                     res++;
17                 }
18                 sum+=f[i];
19                 if(i-k+1>=0) sum-=f[i-k+1];
20             }
21             
22             for(int i=n-k+1; i<n; i++) 
23             {
24                 if((dir[i] + sum) %2== 1) return -1;
25                 if(i-k+1>=0) sum-=f[i-k+1];
26             }
27             return res;
28         }
29 
30         int minKBitFlips(vector<int>& A, int K)
31         {
32             n = A.size();
33             _for(i,0,n)
34                 if(A[i])
35                     dir[i] = 0;
36                 else
37                     dir[i] = 1;
38             return solve(K);
39         }
40 };

经典ACM问题——奶牛掉头