HDU - 6227 Rabbits (贪心)

题意:n个兔子在河边排成一排玩(数轴上),每个兔子都有一个坐标
任意一只兔子可以跳到其余任两只兔子(必须保证它们中间有空位)中间,问最多可移动多少次?
思路:首先我们肯定要尽可能多的利用每两只兔子之间的间隙,去跳(插入)。但是在第一次跳的时候
会损失一个两个兔子之间的间隙。所以我们选两边间隙较小的,用所有的空隙数减去即为所求。(贪心)

完整代码:

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5;
int sub[maxn];
int arr[maxn];
long long ans;
int main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        ans = 0;
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        for(int i =0;i<n-1;i++){
            sub[i] = arr[i+1] -arr[i]-1;
        }
        for(int i=0;i<n-1;i++){
            ans += sub[i];
        }
        cout<<ans-min(sub[0],sub[n-2])<<endl;
    }
}

 

上一篇:不死神兔


下一篇:调试 ambari-server 总结