bzoj 1704: [Usaco2007 Mar]Face The Right Way 自动转身机 — 贪心
Contents
1704: [Usaco2007 Mar]Face The Right Way 自动转身机
Time Limit: 5 Sec Memory Limit: 64 MB
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
BINPUT DETAILS:
B
B
F
B
F
B
BINPUT 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
贪心…先枚举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²)
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define N 5010
char c;bool lj[N],a[N],t;int n,k,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("\n%c",&c);
a[i]=(c=='F'?0:1);
}
for(int i=n;i>0;i--)
{
memset(lj,0,sizeof(lj));t=ans=0;
for(int j=1;j<=n;j++)
{
if(!(a[j]^lj[j-1]^lj[j])) lj[j]^=lj[j-1];
else
{
if(j+i-1<=n) ans++;
else{t=1;break;}
lj[j]=lj[j]^lj[j-1]^1;lj[j+i]^=1;
}
}
if(!t){k=i;break;}
}
printf("%d %d\n",k,ans);
}
发表评论