Submission #156632

---

Source Code Expand

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;

public class Main {
    static BufferedReader br = new BufferedReader(
            new InputStreamReader(System.in));
    static PrintWriter pw = new PrintWriter(System.out);
    
    public static void main(String[] args) throws Exception {

        try {

            String s = solve();
            pw.write(s);
        } finally {
            pw.close();
            br.close();
        }
    
    }

    private static String solve() throws Exception {
        String res = null;

        int n = Integer.parseInt(br.readLine());
        
        int[] array = new int[n + 1];
        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(br.readLine());
        }

        int[] sortArray = Arrays.copyOf(array, n + 1);
        
        Arrays.sort(sortArray);
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= n; j++) {
                if (array[i] == sortArray[j]) {
                    array[i] = j;
                }
            }
        }
        
        
        int count = 0;

        
        for (int i = 0; i < n - 2; i++) {
            if (array[i] != array[i + 1] - 1 &&  array[i] == array[i + 2] - 2) {
                count++;
                int aPos = -1;
                int aNum = -1;
                for (int j = 0; j < n; j++) {
                    if (array[j] == array[i] + 1) {
                        count ++;
                        aPos = j;
                        aNum = array[i] + 1;
                        break;
                    }
                }
                if (aPos == -1 ) {
                    throw new RuntimeException();
                }
                
                if (i + 1 > aPos) {
                    for (int j = aPos; j > aPos; j --) {
                        array[j] = array[j - 1];
                    }
                } else {
                    for (int j = aPos; j < aPos; j ++) {
                        array[j] = array[j + 1];
                    }
                }
                array[aPos] = aNum;
            }
        }

        int maxLen = 0;
        int maxPos = 0;
        int len = 0;
        for (int i = 0; i < n - 1; i++) {
            if (array[i] == array[i + 1] - 1) {
                if (i - maxLen == maxPos) {
                    maxLen++;
                } else {
                    len++;
                    if (len > maxLen) {
                        maxPos = i - len;
                        maxLen = len;
                    }
                }
            } else {
                len = 0;
            }
        }
        
//        int minPos = 0;
        boolean isUpdate = true;
        for (int minPos = 0; minPos < n ; minPos++) {
            isUpdate = false;
            int min = array[minPos];
            int rMinPos = minPos;
            for (int i = minPos + 1; i < n; i++) {
                if (min > array[i] && (!( i > maxPos && i < maxPos + maxLen))) {
                    isUpdate = true;
                    min = array[i];
                    rMinPos = i;
                }
            }
            if (isUpdate) {
                count++;
                for (int i = rMinPos; i > minPos; i --) {
                    array[i] = array[i - 1];
                }
            }
            
        }
        
        
        
        res = String.valueOf(Math.max(0, count - maxLen));
        return res;
    }
 

   
}

Submission Info

Judge Result