Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴Java代码。 O(n)。Java排行榜第一(当时)。C++0ms。带注释

Posted by haqishen at 2015-01-17 13:32:36 on Problem 3185 and last updated at 2015-01-17 13:37:40
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator