Advertisement
spider68

min step to reach destination

Jul 26th, 2020
213
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.55 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. int minstep(int a[],int n){
  4.     int i;
  5.     if(n<=1)return 0;
  6.     if(a[0]==0)return -1;
  7.     int step=a[0],jump=1,dis=a[0];
  8.     for(i=1;i<n;i++){
  9.         if(i==n-1)return jump;
  10.         dis=max(dis,a[i]+i);
  11.         step--;
  12.         if(step==0){
  13.             jump++;
  14.             if(dis<=i)return -1;
  15.             step=dis-i;
  16.         }
  17.     }
  18. }
  19. int main() {
  20.     int i,j,t,n;
  21.     cin>>t;
  22.     while(t--){
  23.         cin>>n;
  24.         int a[n];
  25.         for(i=0;i<n;i++)cin>>a[i];
  26.         cout<<minstep(a,n)<<endl;
  27.     }
  28.    
  29.     return 0;
  30. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement