HDU-6227 Rabbits(法則問題+欲張り水問題)

Rabbits
                    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)                                            Total Submission(s): 2341    Accepted Submission(s): 1210
Problem Description
Here N (N ≥ 3) rabbits are playing by the river. They are playing on a number line, each occupying a different integer. In a single move, one of the outer rabbits jumps into a space between any other two. At no point may two rabbits occupy the same position. Help them play as long as possible
Input
The input has several test cases. The first line of input contains an integer t (1 ≤ t ≤ 500) indicating the number of test cases. For each case the first line contains the integer N (3 ≤ N ≤ 500) described as above. The second line contains n integers a1  ai satisfies 1 ≤ ai ≤ 10000.
Output
For each case, output the largest number of moves the rabbits can make.
Sample Input
5
3
3 4 6
3
2 3 5
3
3 5 9
4
1 2 3 4
4
1 2 4 5
Sample Output
1
1
3
0
1
Source
2017 A CM/IPCCアジア区瀋陽駅-再現試合(東北大学に感謝)
http://acm.hdu.edu.cn/showproblem.php?pid=6227
タイトル:
最初は読めませんでしたが、ブログを見てやっと題意がわかりました.
nの位置をあげて、一番外の2つの1つを選んで他の中間に挿入して、最後の2つの間に他のものがないことを保証して、最大何回挿入することができますかと聞きます.
考え方:
 貪欲な思想は、挿入の回数が最も多いことを保証するために、中間の空が多くてこそ、挿入が多いことを保証しなければならない.実は最初の最外層の2つを探して、誰の中間の隙間が少なくて、それから誰を移動して、彼をそれに隣接する結点に隣接する場所に移動します.そして一歩一歩移動して、隙間を埋めるたびに.
例えば:1 3 6 9  この例は
まず1を4位置にジャンプさせ、今は3 4 6 9です.
さらに3を5位置にジャンプさせ、現在は4 5 6 9
さらに4を7位置にジャンプさせ、現在は5 6 7 9
さらに5を8位置にジャンプさせ、現在は6 7 8.
so、最大4回です.
コード:

#include
using namespace std;
int a[501], sum[501];
int main()
{
	int t;
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		int len = 0; 
		memset(sum, 0, sizeof(sum));
		for(int i = 0; i < n; i++)
			cin >> a[i];
		for(int i = 0; i < n -1 ; i++) {
			sum[i] = a[i+1] - a[i] - 1;
			len += sum[i];
		}
		int Min = min(sum[0], sum[n-2]);
		cout << len - Min << endl;
	}

	return 0;
}