bzoj 1704 [Usaco2007 Mar]Face The Right Way 自动转身机( 贪心 )

[Usaco2007 Mar]Face The Right Way 自动转身机

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 497 Solved: 298
[Submit][Status][Discuss]

Description

农夫约翰有N(1≤N≤5000)只牛站成一排，有一些很乖的牛朝前站着．但是有些不乖的牛却朝后站着．农夫约翰需要让所有的牛都朝前站着．幸运的是约翰最近买了一个自动转身机．这个神奇的机器能使K(1≤K≤N)只连续的牛转身．因为约翰从来都不改变K的价值，请帮助他求出K，使旋转次数M达到最小．同时要求出对应的M.

Input

第1行：整数N.

第2行到第N+1行：第i+l行表示牛j的朝向，F表示朝前，B表示朝后．

Output

一行两个数，分别是K和M，中间用空格隔开

Sample Input

7
B
B
F
B
F
B
B

INPUT DETAILS:

There are seven cows and they are facing backward, backward, forward,
backward, forward, backward, and backward, respectively.

Sample Output

3 3

OUTPUT DETAILS:

For K = 3, the machine must be operated three times: turn cows (1,2,3),
(3,4,5), and finally (5,6,7):

B > F F F
B > F F F
F > B > F F
B B > F F
F F > B > F
B B B > F
B B B > F

HINT

当K=3时神奇的机器旋转3次：(1，2，3)，(3，4，5)，和(5，6，7)

Source

Gold

题解：

　　贪心，判断即可。

　　贪心...先枚举k, 然后从左往右扫一遍, 发现位置p的牛的状态不符合就将 [p, p + k ) 的牛都转身,

　　假如p + k - 1 已经超过了最右边牛的位　　置那这个k就不符合要求. 符合要求的就可以用来更

　　新answer.这个贪心的正确性是很显然的.前p - 1头牛都已朝前, 再改动它们也做不到更优; 而要

　　让第p头牛转身, 那就只能让[p, p + k )的牛转身.

　　考虑如何判断位置p的牛的状态, 我们发现p的状态与它本身和[ p - k - 1, p )这个区间内的牛的

　　转身次数有关, 因为转身两次相当于没转, 用异或进行操作可以做到O(1). 枚举O(n), 扫描O(n), 总时间复杂度为O(n²)

 1 #include<cstring>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<cstdio>
 6 
 7 #define N 5007
 8 using namespace std;
 9 inline int read()
10 {
11     int x=0,f=1;char ch=getchar();
12     while(ch>'9'||ch<'0'){if (ch=='-') f=-1;ch=getchar();}
13     while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
14     return x*f;
15 }
16 
17 int n;
18 int f[N],tmp[N],turn[N],ans[N];
19 
20 void input()
21 {
22     char s[10];
23     n=read();
24     for(int i=1;i<=n;i++)
25         scanf("%s",s),f[i]=s[0]=='B';
26 }
27 void work(int k)
28 {
29     int i, cnt=0;
30     for(i=1;i<=n;i++)tmp[i]=f[i],turn[i]=0;
31     for(i=1;i<=n;i++)
32     {
33         tmp[i]^=cnt;
34         if(i<=n-k+1 and tmp[i])cnt^=1,turn[i]=1,ans[k]++;
35         if(i>n-k+1 and tmp[i])ans[k]=n+1;
36         if(i>=k)cnt^=turn[i-k+1];
37     }
38 }
39 int main()
40 {
41     int i, a=1;
42     input();
43     for(i=1;i<=n;i++)work(i);
44     for(i=2;i<=n;i++)if(ans[i]<ans[1])a=i,swap(ans[i],ans[1]);
45     printf("%d %d",a,ans[1]);
46 }