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