Rabbits(跳兔子)

题目大意:

一些坑;

有的坑里面有兔子,有的没有;

坑按顺序排着;

边上的兔子两个兔子可以调到中间有坑的两个兔子之间;

问最多跳多少次;

结束状态是这些兔子之间没有坑了;

对于第一次跳跃,我肯定要拿离团体最近的那个两边

然后跳跃的位置为旁边兔子的旁边

比如   1  3  6  9  

先拿1  跳跃到  位置4 ,样例变为   3  4  6  9

然后  3跳到5的位置····这样挨着跳,可以不浪费空间,尽量多跳

 然后跳到    4   5   6  9   

再用4跳到7

这样就会发现,每跳一次只减少一个空位

那么把几只兔子所有的中间空位加起来

进去刚开始第一只兔子隔掉的,那么就是可以玩几次

这个题目就是不知道从哪里开始跳的(两边都可以跳)

所以说

ans-=min(a[2]-a[1]-1,a[n]-a[n-1]-1)

 

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
int a[maxn]; 
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        int ans=0;
        for(int i=2;i<=n;i++){
            ans+=(a[i]-a[i-1]-1);
        }
        int mi=min(a[2]-a[1]-1,a[n]-a[n-1]-1);
        cout<<ans-mi<<endl; 
    } 
}

 

上一篇:MySQL高可用读写分离方案预研


下一篇:有一对兔子,从出生后第3个月起每个月都生一对兔子(超简单解释)