toj 3474 解题报告

这道题的解题思路：就递归二分到剩两个时，把这两个数相乘加到结果sum中累加，注意当二分到只剩一位的时候就抛弃，左边的应该等于右边的或者多一位。

解题关键题目的提示：

Consider a dance with 11 cows numbered 1..11. Here is the sequence of dividing them:

1     2     3     4     5     6  |  7     8     9     10     11

    1     2     3  |  4     5     6

        1     2  |  3
                1  2        => 1*2=2 added to sum -> sum=2
                3           => sent home with rose

        4     5  |  6
                4  5        => 4*5=20 added to sum -> sum=22
                6           => sent home with rose

    7     8     9  | 10    11

        7     8  |  9
                7  8        => 7*8=56 added to sum -> sum=78
                9           => sent home with rose
        10    11            => 10*11=110 added to sum -> sum=188

So the sum for this dance would be 188.

import java.util.Scanner;

public class Main3474 {

	private static long sum = 0;

	public static void mid(int[] arr, int size) {
		if (size == 2) {
			sum += (arr[0] * arr[1]);
			return;
		} else if (size == 1)
			return;
		// int mid = ((Double) StrictMath.ceil((double) size / 2)).intValue();
		int mid = (size >> 1) + (size & 1);//size >> 1 相当于size/2 ; size & 1相当于 size % 2
	   // System.out.println("mid=" + mid);
		int[] leftArr = new int[mid];
		int[] rightArr = new int[size - mid];
		System.arraycopy(arr, 0, leftArr, 0, leftArr.length);
		System.arraycopy(arr, mid, rightArr, 0, rightArr.length);
		mid(leftArr, mid);
		mid(rightArr, rightArr.length);
		
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		while (sc.hasNextInt()) {
			sum = 0;
			int size = sc.nextInt();
			int[] arr = new int[size];
			for (int i = 0; i < size; ++i) {
				arr[i] = i + 1;
			}
			Main3474.mid(arr, arr.length);
			System.out.println(sum);
		}
	}

}

其中，当一个int型的数除以2的幂时，可以用右移，此时原数与（&）上右移的位数就可以得到余数。