Задача взята с сайта e-olymp.com.

Условие

Как известно, Андрей Сергеевич — ярый коллекционер бабочек. Он имеет огромную коллекцию, экспонаты которой собраны со всего мира. Будем считать, что в мире существует 2000000000 видов бабочек.

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

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

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

В первой строке входного файла содержится единственное число N (1 ≤ N≤ 100000) — количество видов бабочек в коллекции Андрея Сергеевича.

В следующей строке через пробел находятся N упорядоченных по возрастанию чисел — номера видов бабочек в коллекции.

Все виды бабочек в коллекции имеют различные номера.

В третьей строке файла записано число M (1≤ M≤ 100000) — количество видов бабочек, про которых Андрей Сергеевич хочет узнать, есть ли они у него в коллекции или же нет. В последней строке входного файла содержатся через пробел M чисел — номера видов бабочек, наличие которых необходимо проверить.

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

Выходной файл должен содержать M строчек. Для каждого запроса выведите «YES«, если бабочка с данным номером содержится в коллекции, и «NO» — в противном случае.

Тесты:

№	Входные данные	Выходные данные:
1	7 10 47 50 63 89 90 99 4 84 33 10 82	NO NO YES NO
2	10 1 4 7 11 12 43 44 67 344 355 5 1 2 4 44 45	YES NO YES YES NO

Код на Java:

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

class Main {
	public static boolean find(int search, int[] arr, int len) {
		boolean ret = false;
		int fst = 0;
		int lst = len - 1;
		while (fst <= lst) {
			int mid = (fst + lst) / 2;
			if (search == arr[mid]) {
				ret = true;
				break;
			} else if (search < arr[mid]) {
				lst = mid - 1;
			} else {
				fst = mid + 1;
			}
		}
		return ret;
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int len = scan.nextInt();
		int[] arr = new int[len];
		int i;
		for (i = 0; i < len; i++) {
			arr[i] = scan.nextInt();
		}
		int num = scan.nextInt();
		int search;
		for (i = 0; i < num; i++) {
			search = scan.nextInt();
			System.out.print((find(search, arr, len))? "YES\n" : "NO\n");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static boolean find(int search, int[] arr, int len) {

boolean ret = false;

int fst = 0;

int lst = len - 1;

while (fst <= lst) {

int mid = (fst + lst) / 2;

if (search == arr[mid]) {

ret = true;

break;

} else if (search < arr[mid]) {

lst = mid - 1;

} else {

fst = mid + 1;

}

return ret;

}

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int len = scan.nextInt();

int[] arr = new int[len];

int i;

for (i = 0; i < len; i++) {

arr[i] = scan.nextInt();

}

int num = scan.nextInt();

int search;

for (i = 0; i < num; i++) {

search = scan.nextInt();

System.out.print((find(search, arr, len))? "YES\n" : "NO\n");

}

Алгоритм:

Вначале считываем необходимые нам значения: размер коллекции len, элементы коллекции (массив arr) и количество проверяемых экспонатов num:

Scanner scan = new Scanner(System.in);
int len = scan.nextInt();
int[] arr = new int[len];
int i;
for (i = 0; i < len; i++) {
	arr[i] = scan.nextInt();
}
int num = scan.nextInt();

Scanner scan = new Scanner(System.in);

int len = scan.nextInt();

int[] arr = new int[len];

int i;

for (i = 0; i < len; i++) {

arr[i] = scan.nextInt();

}

int num = scan.nextInt();

Затем по очереди считываем номера проверяемых экспонатов, ищем их в массиве, используя алгоритм бинарного поиска, и затем сообщаем о наличии или отсутствии экспоната:

int search;
for (i = 0; i < num; i++) {
	search = scan.nextInt();
	System.out.print((find(search, arr, len))? "YES\n" : "NO\n");
}

int search;

for (i = 0; i < num; i++) {

search = scan.nextInt();

System.out.print((find(search, arr, len))? "YES\n" : "NO\n");

}

Суть алгоритма бинарного поиска: искомый элемент сравнивается с элементом в середине диапазона. При совпадении поиск считаем оконченным. Если совпадения нет, то, в зависимости от различия, поиск продолжается в «левой» или «правой» половине текущего диапазона. Если оказалось, что очередной диапазон имеет «нулевую» длину, это означает, что искомого элемента в исходном массиве нет. Примечание: алгоритм требует упорядоченности исходного массива по возрастанию или убыванию.

public static boolean find(int search, int[] arr, int len) {
	boolean ret = false;
	int fst = 0;
	int lst = len - 1;
	while (fst <= lst) {
		int mid = (fst + lst) / 2;
		if (search == arr[mid]) {
			ret = true;
			break;
		} else if (search < arr[mid]) {
			lst = mid - 1;
		} else {
			fst = mid + 1;
		}
	}
	return ret;
}

public static boolean find(int search, int[] arr, int len) {

boolean ret = false;

int fst = 0;

int lst = len - 1;

while (fst <= lst) {

int mid = (fst + lst) / 2;

if (search == arr[mid]) {

ret = true;

break;

} else if (search < arr[mid]) {

lst = mid - 1;

} else {

fst = mid + 1;

}

return ret;

}

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

Facebook
X
Shares

java@Cat

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

e-olymp 3966. An ardent collector of butterflies

Условие

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

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

Тесты:

Код на Java:

Алгоритм:

Ссылки:

Добавить комментарий Отменить ответ