学步园

 这道题的解题思路：就递归二分到剩两个时，把这两个数相乘加到结果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;</p> <p>public class Main3474 {</p> <p> private static long sum = 0;</p> <p> public static void mid(int[] arr, int size) {<br /> if (size == 2) {<br /> sum += (arr[0] * arr[1]);<br /> return;<br /> } else if (size == 1)<br /> return;<br /> // int mid = ((Double) StrictMath.ceil((double) size / 2)).intValue();<br /> int mid = (size >> 1) + (size & 1);//size >> 1 相当于size/2 ; size & 1相当于 size % 2<br /> // System.out.println("mid=" + mid);<br /> int[] leftArr = new int[mid];<br /> int[] rightArr = new int[size - mid];<br /> System.arraycopy(arr, 0, leftArr, 0, leftArr.length);<br /> System.arraycopy(arr, mid, rightArr, 0, rightArr.length);<br /> mid(leftArr, mid);<br /> mid(rightArr, rightArr.length);</p> <p> }</p> <p> public static void main(String[] args) {</p> <p> Scanner sc = new Scanner(System.in);<br /> while (sc.hasNextInt()) {<br /> sum = 0;<br /> int size = sc.nextInt();<br /> int[] arr = new int[size];<br /> for (int i = 0; i < size; ++i) {<br /> arr[i] = i + 1;<br /> }<br /> Main3474.mid(arr, arr.length);<br /> System.out.println(sum);<br /> }<br /> }</p> <p>}<br />

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