先说一下题目大意：

　　N头牛排成一列1<=N<=5000。每头牛或者向前或者向后。为了让所有牛都 面向前方，农夫每次可以将K头连续的牛转向1<=K<=N，求操作的最少 次数M和对应的最小K。

 

可能有点不好理解，实在理解不了可以看一下原题，模拟一下样例。下面直接说思路。

先模拟样例

0 0 1 0 1 0 0（0表示朝向后方，1表示朝向前方）

• 可以看到我们所进行的调整一定是从左端或者右端开始的（因为从中间开始对前后造成的影响是难以控制的）

• 在我们转牛的过程中对于每一段一定是从第一个 0 开始进行转向。

 

到这里思路已经明了，但是有一个问题：

交上去T了，怎么办？

这就要用到神奇的小东东——差分 了

想一想怎么差分？

具体过程不多说了，差分我会在代码里写上注释。

下面是很精简的代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn = 10009;
 7 int n;
 8 int A[maxn],B[maxn];//B数组为差分数组 
 9 int main(){
10     //freopen("a.in","r",stdin); 
11     scanf("%d",&n);
12     char ch;
13     for(int i=1;i<=n;++i){
14         cin>>ch;A[i]=ch=='B'?0:1;//3目运算符，很巧妙。 
15     }
16     int Min=0x7fffffff,ans;//Min是K的最小值 ， ans是反转次数。 
17     for(int len=1;len<=n;++len){//列举K 
18         memset(B,0,sizeof B);//别忘了 
19         bool b=0,flag=1;int cnt=0;//注意3个变量的含义 
20         for(int i=1;i<=n;++i){
21             b^=B[i];//用的是位运算 
22             if(!(A[i]^b)){//差分开始 
23                 if(i+len-1>n){flag=0;break;}
24                 b^=1,B[i+len]^=1;
25                 ++cnt;
26             }//差分结束 
27         }
28         if(flag){if(cnt<Min)Min=cnt,ans=len;}
29     }
30     printf("%d %d\n",ans, Min);
31 }