题意：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; } }
转载于:https://www.cnblogs.com/Tianwell/p/11348108.html
