Submission #72893261

---

Source Code Expand

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().D();
	}
	
	
	public void A() {
		Scanner in = new Scanner(System.in);
		String s = in.next();

		System.out.println(s+"s");
	}
	
	public void B() {
		Scanner in = new Scanner(System.in);
		long N = in.nextInt();
		long K = in.nextInt();
		long sum=0;
		int year=0;
		
		while ( true ) {
			sum+=N;
			if ( sum>=K ) break;
			N++;
			year++;
		}
		System.out.println(year);
		
	}

	public void C() {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		long T = in.nextLong();
		
		long[] A = new long[N];
		for (int i=0;i<N;i++) A[i] = in.nextLong();
		
		long prev=0;
		boolean open = false;
		int idx = 0;
		long score = 0;
		
		for (long t=0;t<T;t++) {
			if ( t==0 ) open=true;
			if ( idx < N && A[idx]==t ) {
				idx++;
				if (open) { open=false;prev=0;}
			}
			if ( !open && prev==100 ) {open=true;prev=0;}

			prev++;
			if ( open ) score++;
		
		}
		
		System.out.println(score);
	}

	public void D() {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();

		for (int i=0;i<T;i++) {
			int N = in.nextInt();
			Pos[] R = new Pos[N];
			Pos[] P = new Pos[N];
			
			for (int j=0;j<N;j++) {
				int y = in.nextInt();
				R[j] = new Pos(j,y);
				P[j] = R[j];
			}

//			System.err.println("turn="+i);
//			for ( Pos p : R ) System.err.print(p.toString() + "  ");
//			System.err.println("");
			
			long step = 0;
			int idx=0;
			while (idx<N) {
				Arrays.sort(P);
//				for ( Pos p : R ) System.err.print(p.toString() + "  ");
//				System.err.println("");
				//左を捜査
				int x = P[idx].x;
				idx++;
				if ( x>0 ) {
					int x2=x-1;
					int d = R[x2].y-R[x].y;
					if ( d>1 ) {
						R[x2].y -=(d-1);
						step += (d-1);
					}
				}
				if ( x<N-1 ) {
					int x2=x+1;
					int d = R[x2].y-R[x].y;
					if ( d>1 ) {
						R[x2].y -=(d-1);
						step += (d-1);
					}
				}
			}
			System.out.println(step);
		}
	}


}

class Pos implements Comparable<Pos> { 
	public Pos(int j, int i) {
		this.x = j;
		this.y = i;
	}

	int x,y;
	
	public String toString() {
		return x + "," + y;
	}
	
	  @Override
	  public int compareTo( Pos p ){
		  if ( this.y == p.y ) {
			  return this.x - p.x;
		  } else {
			    return this.y - p.y;
		  }
	  }
}

Submission Info

Judge Result