| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴Java代码。 O(n)。Java排行榜第一(当时)。C++0ms。带注释import java.io.*;
public class Main{
// 前后中3个bowls都需要转向,所以创建这个数组
static int di[] = {-1,0,1};
// 记录输入时的状态
static int bowls[];
// 记录翻转状态,1表示当前bowl翻转过,0表示没有
static int f[];
static int ans = 21;
// 获取当前bowl的方向,返回值为1或者0
static int get(int m){
// sum是当前bowl状态+前中后3个点的翻转状态
// 是奇数则返回1,偶数返回0
int sum = bowls[m];
for(int i = 0; i < 3; i++){
if(m+di[i] < 0) continue;
if(m+di[i] >=20) continue;
sum += f[m+di[i]];
}
return sum%2;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input[] = br.readLine().split("\\s");
bowls = new int[20];
for(int i = 0; i < 20; i++)
bowls[i] = new Integer(input[i]);
// 接下来是核心
// 首先需要明白两点:
// 一:同一个bowl不需要翻转两次以上。
// 二:bowl的翻转顺序不影响最终结果
// 基于以上两点,先枚举第一个bowl的情况(其实就2种。。)
for(int first = 0; first < 2; first++){
f = new int [20];
f[0] = first;
// 然后扫描后面19个bowls
for(int i = 1; i < 20; i++){
// 如果上一个bowl是1,则要翻转当前bowl
if(get(i-1) == 1){
f[i] = 1;
}
}
// 判断最后一个bowl是0还是1;
// 如果是0则输出答案,因为题目说明了所有输出都能输出结果,所以这一步判断并不是必要的。但其他的翻转题目里这是必须的。
if(get(19) == 0){
int count = 0;
// 把翻转数组f里全部值相加就是总翻转次数了。
for(int i : f){
count += i;
}
ans = Math.min(ans, count);
}
}
System.out.println(ans);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator