[Logo] Форум DL
  [DL]  На главную страницу 
Индекс форума ->Олимпиадное программирование ->USACO Analyses
Автор Сообщение
Михаил Долинский

Темы: 1440
Сообщений: 34071

Мой профиль
Analysis by Nick Wu)
In this problem, we're given a list of $N$ integers, with the guarantee that removing exactly one of them can result in a sorted array.

Because removing one of them can result in a sorted array, if we consider the elements that are not in the right order, those must form a sequence that is almost sorted, except that either the minimum element is in the rightmost slot or the maximum element is in the leftmost slot. Consequently, if there are $K$ elements that are out of order, it will take $K-1$ swaps to fix them, since every swap except for the last one can only fix the location of one such element.


import java.io.*;
import java.util.*;
public class outofplace {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("outofplace.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("outofplace.out")));

		int n = Integer.parseInt(br.readLine());
		int[] height = new int[n];
		int[] sorted = new int[n];
		for(int i = 0; i < n; i++) {
			height[i] = Integer.parseInt(br.readLine());
			sorted[i] = height[i];
		}
		Arrays.sort(sorted);
		int swaps = -1;
		for(int a = 0; a < n; a++) {
			if(sorted[a] != height[a]) {
				swaps++;
			}
		}
		swaps = Math.max(0, swaps);
		pw.println(swaps);
		pw.close();
	}
	
}

 
Индекс форума ->Олимпиадное программирование ->USACO Analyses
Time:0,031