题意: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; } }