e-olymp 2662. Метод минимума

20/11/2020 by Виктория Крачилова

Условие задачи

Массив сортируется методом выбора по возрастанию. Сколько раз меняет свое место первый по порядку элемент?

Входные данные

Первая строка содержит количество элементов в массиве $n$ $\left(1\leqslant n\leqslant1000\right)$. Во второй строке задан сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10^9$.

Выходные данные

Вывести количество перемещений первого элемента.

Тесты

№	Ввод	Вывод
1	3 1 3 2	0
2	2 2 1	1
3	4 4 1 5 3	3
4	6 23 5 56 2 87 3	1
5	7 15 1 6 3 9 8 13	4

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		java.util.Scanner in = new java.util.Scanner(System.in);
		int n = in.nextInt();
		int []x = new int [n];
	    int counter = 0; // количество перемещений
	    for (int i = 0; i < n; i++){
	        x[i] = in.nextInt();
	    }
	    int first = x[0]; // первый по порядку элемент
	    for (int i = 0; i < n - 1; i++) {
	        int min = i; // индекс минимального элемента
	        for (int j = i + 1; j < n; j++) {
	            if (x[j] < x[min]) min = j;
	        }
	        if((x[i] == first || x[min] == first) && x[i] != x[min]) counter ++;
	        int t = x[i];
		    x[i] = x[min];
		    x[min] = t;
	    }
    	System.out.print(counter);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

java.util.Scanner in = new java.util.Scanner(System.in);

int n = in.nextInt();

int []x = new int [n];

int counter = 0; // количество перемещений

for (int i = 0; i < n; i++){

x[i] = in.nextInt();

}

int first = x[0]; // первый по порядку элемент

for (int i = 0; i < n - 1; i++) {

int min = i; // индекс минимального элемента

for (int j = i + 1; j < n; j++) {

if (x[j] < x[min]) min = j;

}

if((x[i] == first || x[min] == first) && x[i] != x[min]) counter ++;

int t = x[i];

x[i] = x[min];

x[min] = t;

}

System.out.print(counter);

}

Решение

Применяем метод выбора по возрастанию. Для этого мы ищем наименьший элемент в массиве и перемещаем его на первое место. Затем ищем второй наименьший элемент и перемещаем его уже на второе место после первого наименьшего элемента. Этот процесс продолжается до тех пор, пока в массиве не закончатся неотсортированные элементы. Для того, чтобы найти количество перемещений первого элемента, мы проверяем совпадает ли значение первого элемента со значениями перемещаемых элементов. Также смотрим, чтобы значения этих элементов не были равны между собой, так как в этом случае сам элемент никуда не сдвигается.

Подробное изложение алгоритма сортировки можно найти в этой статье .

Ссылки

e-olymp 9410. Студенческая любовь

18/09/2020 by Дмитрий Воротов

Задача

Нурдаулет и Жарасхан тренируют студентов. К каждому студенту у них имеется свое собственное отношение, которое выражается как числа $a_{i}$ (для Нурдаулета) и $b_{i}$ (для Жараскана), которые называются индексом любви студентов. Аскар попросил их рассчитать коэффициент несправедливого отношения. Коэффициент несправедливого отношения — это разница между самым большим и самым маленьким индексом любви. Чтобы не показывать свои, возможно, большие коэффициенты несправедливого отношения, они решили обмануть: каждый перемешивает свой массив, после чего формируется новый массив $c_{i}$ = $a_{i}$ + $b_{i}$, и его коэффициент несправедливого отношения передается Аскару. Какое минимально возможное значение коэффициента они могут достичь?

Входные данные

Первая строка содержит одно целое число $n$ $(1 ⩽ n ⩽ 200000)$. Вторая строка содержит $n$ целых чисел $a_{i}$ $(-10^6 ⩽ a_{i} ⩽ 10^6)$. Третья строка содержит $n$ целых чисел $b_{i}$ $(-10^6 ⩽ b_{i} ⩽ 10^6)$.

Выходные данные

Выведите одно число — ответ на задачу.

Тесты

№	Входные данные	Выходные данные
1	2 -3 -5 3 5	0
2	1 5 -2	0
3	5 -5 -2 -1 0 4 5 4 0 0 -1	4
4	9 1000 -22 333 -56 1 2 -77 -650 10 -7 166 -333 90 -565 12 788 -800 111	523

Код программы

import java.util.*;
import java.io.*;

class Main
{
	public static void main(String[] args) throws java.lang.Exception {
	    Scanner in = new Scanner(System.in);
    	PrintWriter out = new PrintWriter(System.out);
	    int n;
	    n = in.nextInt();
	    int[] a = new int[n];
	    int[] b = new int[n];
	    for (int i = 0; i < n; i ++) a[i] = in.nextInt(); // Считываем массивы
	    for (int i = 0; i < n; i ++) b[i] = in.nextInt();  
	    Arrays.sort(a);// Сортируем массивы
	    Arrays.sort(b);// Вместо сортировки по убыванию будем просматривать отсортированный массив в обратном порядке
	    for (int i = 0; i < n; i ++) a[i] += b[n - i - 1];  // Суммируем элементы
	    int maxa = a[0], mina = a[0];
	    for (int i = 0; i < n; i ++) {
	        maxa = Math.max(maxa, a[i]);    // Находим минимальный и максимальный элементы
	        mina = Math.min(mina, a[i]);     
	    }
		out.println(maxa - mina);// Разность минимального и максимального и будет самым маленьким индексом любви 
		out.flush();
	}
}

import java.util.*;

import java.io.*;

class Main

{

public static void main(String[] args) throws java.lang.Exception {

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

int n;

n = in.nextInt();

int[] a = new int[n];

int[] b = new int[n];

for (int i = 0; i < n; i ++) a[i] = in.nextInt(); // Считываем массивы

for (int i = 0; i < n; i ++) b[i] = in.nextInt();

Arrays.sort(a);// Сортируем массивы

Arrays.sort(b);// Вместо сортировки по убыванию будем просматривать отсортированный массив в обратном порядке

for (int i = 0; i < n; i ++) a[i] += b[n - i - 1]; // Суммируем элементы

int maxa = a[0], mina = a[0];

for (int i = 0; i < n; i ++) {

maxa = Math.max(maxa, a[i]); // Находим минимальный и максимальный элементы

mina = Math.min(mina, a[i]);

}

out.println(maxa - mina);// Разность минимального и максимального и будет самым маленьким индексом любви

out.flush();

}

Решение

Коэффициент будет минимальным в том случае, когда все элементы массива $c_{i}$ будут отличаться друг от друга как можно меньше. Для этого отсортируем один массив по убыванию, другой — по возрастанию и почленно сложим. После этого останется только найти максимальный и минимальный элементы полученного массива.

Ссылки

Условие задачи e-olymp

Код решения ideone

e-olymp 2166: Анаграммы

29/08/2016 by Иоанна Васильева

Задача

Слово называется анаграммой другого слова, если оно может быть получено перестановкой его букв.

Входные данные

Два слова заданы в отдельных строках. Слова состоят из строчных латинских букв и цифр. Длины слов не превышают 255.

Выходные данные

Следует вывести «YES«, если введенные слова являются анаграммами друг друга и «NO» если нет.

Решение

В задаче требуется определить являются ли два введенных слова анаграммами.
Основная проблема состоит в том, что буквы находятся в словах на различных позициях и это мешает нам просто сравнить строки. Поэтому упорядочим символы в строке по алфавиту с помощью метода Arrays.sort, который вызываем в функции sortString, которая вернет нам новую отсортированную строку.
Теперь мы можем выполнить сравнение строк с помощью функции equals(), которая вернет нам true только в том случае, если строки идентичны. В таком случае и выводим «YES», а в противном случае «NO».

Код

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String word1, word2;
		word1 = in.nextLine();
		word2 = in.nextLine();
		if (sort(word1).equals(sort(word2))) {
			System.out.print("YES");
		}
		else System.out.print("NO");
	}
	static String sort(String word1) {
		char[] content = word1.toCharArray();
		Arrays.sort(content);
		return new String(content);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

String word1, word2;

word1 = in.nextLine();

word2 = in.nextLine();

if (sort(word1).equals(sort(word2))) {

System.out.print("YES");

}

else System.out.print("NO");

}

static String sort(String word1) {

char[] content = word1.toCharArray();

Arrays.sort(content);

return new String(content);

}

На Ideone.

Тест

Входные данные	Выходные данные
sharm marsh	YES
ananas nnaass	NO
tommarvoloriddle iamlordvoldemort	YES

Ссылка на задачу на e-olimp и на ее решение.

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: сортировка

e-olymp 2662. Метод минимума

Условие задачи

Входные данные

Выходные данные

Тесты

Код программы

Решение

Ссылки

e-olymp 9410. Студенческая любовь

Задача

Входные данные

Выходные данные

Тесты

№

Входные данные

Выходные данные

Код программы

Решение

Ссылки

e-olymp 2166: Анаграммы

Входные данные

Выходные данные

Решение

Код

Тест