题目(Topcoder锦标赛187 250题):
Problem Statement
+---+
| D |
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
| C |
+---+
The ASCII art above shows the net of a general 6-sided die. There is a number written on each of the six sides. In the picture, these numbers are denoted A to F. (The net is folded so that the numbers are on the outside, but this information is not necessary to solve the following problem.)
The numbers A to F will be given to you as a int[] values, where A will be values[0], B will be values[1], and so on.
You have N^3 identical dice, each one matching the net shown above. You want to take all the dice, rotate some of them, and assemble a N×N×N cube. The cube will be standing on a table, hence only 5 of its sides will be visible.
You are given the int N, and the int[] values. Write a method that will return the smallest possible sum of the 5N^2 visible faces of the dice.
Definition
Class:
CubeOfDice
Method:
minimumSum
Parameters:
int, int[]
Returns:
long
Method signature:
long minimumSum(int N, int[] values)
(be sure your method is public)
Constraints
-
N will be between 1 and 1,000,000, inclusive.
-
values will contain exactly 6 elements.
-
Each element of values will be between 1 and 50, inclusive.
Examples
0)
2
{1,2,3,4,5,6}
Returns: 36
This input corresponds to 8 classical dice.
1)
3
{1,2,3,4,5,6}
Returns: 69
Now we have 27 classical dice.
2)
1000000
{50,50,50,50,50,50}
Returns: 250000000000000
The largest possible output. Note that all numbers are equal, hence in this case there is only one possible way to arrange the dice.
3)
10
{1,1,1,1,50,1}
Returns: 500
It is possible to rotate and arrange the dice so that no side with the 50 will be visible.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
思路:找出露出一面, 两面, 和三面的色子数, 计算色子露出一面至三面的时候露出的数字最小和. 再求总和即可.
代码:
package jyu.topcoder._187;
import java.util.ArrayList;
import java.util.Collections;
public class CubeOfDice {
/**
* 求由色子组成的立方体的5个可见面(底部不算)中所有数字最小之和.
* @param args
*/
public static void main(String[] args) {
long startTime=System.currentTimeMillis(); //获取开始时间
CubeOfDice cod = new CubeOfDice();
// int N = 3;
// int[] values = new int[]{1,2,3,4,5,6};
// int N = 1000000;
int[] values = new int[]{50,50,50,50,50,50};
int N = 1;
// int[] values = new int[]{22,27,45,12,50,46};
System.out.println(cod.minimumSum(N, values));
long endTime=System.currentTimeMillis(); //获取结束时间
System.out.println("程序运行时间： "+(endTime-startTime)+"ms");
}
/**
* 求由色子组成的立方体的5个可见面(底部不算)中所有数字最小之和.
* @param N 色子数
* @param values 色子各面的数值
* @return ret 可见的色子面所有数字最小之和
* 色子的各面数字分布,按A-F分配values[0] - values[5]的值
* +---+
| D |
+---+---+---+---+
| E | A | B | F |
+---+---+---+---+
| C |
+---+
*/
public long minimumSum(int N, int[] values){
//当色子6面的数字都一样时
long sum = 0;
for (int i = 0; i < values.length; i++) {
sum += values[i];
}
if(sum == values[0] * values.length) return (long)N * N * values[0] * 5;
//当只有一个色子时
if(N == 1) {
sum = 0;
int max = 0;
for (int i = 0; i < values.length; i++) {
sum += values[i];
max = Math.max(max, values[i]);
}
return sum - max;
}
//根据每个色子的坐标来判断该色子可见面有多少
int one = 0 , two = 0, three = 0;
for (int i = 0; i < N; i ++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
int type = diceType(i, j, k, N - 1);
switch (type) {
case 0:
k = N - 2;
break;
case 1:
one++;
break;
case 2:
two++;
break;
case 3:
three++;
break;
default:
break;
}
}
}
}
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < values.length; i++) {
list.add(values[i]);
}
Collections.sort(list);
//求色子可见面为1-3时的最小数字和
int pointOne = list.get(0);
int pointTwo = pointOne + list.get(1);
int pointThree = pointTwo + list.get(2);
int ret = pointThree * three + pointTwo * two + pointOne * one;
return ret;
}
/**
* 判断给定坐标位置的色子有几面可见, 返回可见数.
* @param x 横坐标
* @param y 纵坐标
* @param z 高坐标
* @param N 坐标最大值
*
* @return 可见的色子面
*/
public int diceType(int x, int y, int z , int N){
int one = 0 , two = 0, three = 0;
if(x == 0 || x == N) one = 1;
if(y == 0 || y == N) two = 1;
if(z == N) three = 1;
return (one + two + three);
}
}
总结: 思维上有进步, 继续努力!