【HDOJ6227】Rabbits（贪心）

题意：有n个位置，每次可以选其中一个往另外其它两个位置的中间插（如果有空的话），问最多能插几次

3<=n<=500

1 ≤ ai ≤ 10000

思路：显然可以把所有的空都利用起来

但最左最右两边的空必须选一边放弃

判断一下两种里面哪种更优就行了

感谢队友带我飞

 1 #include <stdio.h>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <string.h>
 5 #include <limits.h>
 6 #include <string>
 7 #include <iostream>
 8 #include <queue>
 9 #include <math.h>
10 #include <stack>
11 #include <map>
12 #define left (now<<1)
13 #define right ((now<<1)+1)
14 #define mid ((l+r)>>1)
15 using namespace std;
16 typedef long long int lint;
17 
18 const int MAXN = 1e5 + 10;
19 const int MOD = 1e9 + 7;
20 
21 int n,t,a[MAXN];
22 lint ans1,ans2,ans;
23 
24 int main(){
25     int t; scanf("%d",&t);
26     while(t--){
27         scanf("%d",&n); ans1 = ans2 = ans = 0;
28         for(int i = 1; i <= n; ++i){
29             scanf("%d",&a[i]);
30         }
31         for(int i = 2; i < n; ++i){
32             ans1 += 1ll * a[i + 1] - a[i] - 1;
33         }
34         for(int i = n - 1; i > 1; --i){
35             ans2 += 1ll * a[i] - a[i - 1] - 1;
36         }
37         ans = max(ans1,ans2);
38         printf("%I64d
",ans);
39     }
40     return 0;
41 }