Решение задачи Эффективный подход с Codeforces

Без пояснения   Просмотров: 28


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

Линейный поиск, по мнению мальчиков, работает следующим образом. В заранее выбранном порядке элементы массива поочередно сравниваются с числом, которое требуется найти. Как только найден элемент массива, равный искомому, поиск завершается. Эффективностью алгоритма считается количество совершенных сравнений. Чем меньше линейный поиск совершил сравнений, тем он эффективнее.

Вася убежден, что линейный поиск будет работать эффективнее, если последовательно перебирать элементы, начиная с 1-го (в задаче считается, что элементы массива проиндексированы от 1 до n) и заканчивая n-м. А Петя говорит, что Вася неправ: меньше сравнений понадобится, если перебирать последовательно элементы, начиная с n-го и заканчивая 1-м. Саша утверждает, что оба подхода равноценны.

Чтобы наконец приступить к задаче, сокомандники решили положить конец спорам, сравнив два подхода на примере. Для этого они взяли массив, являющийся перестановкой целых чисел от 1 до n, а также сгенерировали m запросов вида: найти в массиве элемент со значением b i. Они хотят для обоих подходов посчитать, сколько сравнений суммарно понадобится линейному поиску, чтобы ответить на все запросы. Если меньше сравнений понадобится сделать первому подходу, то победителем в споре будет считаться Вася. Если второму — Петя. Если же оба подхода выполнят одинаковое количество сравнений, верх в споре одержит Саша.

Но вот незадача: линейный поиск работает слишком медленно. Поэтому до конца тренировки мальчики так и не узнают, кто же был прав, если не вмешаться вовремя. Помогите ребятам определить, кто победит в споре.

Код

#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long  i, x, n, m, c = 0, s = 0;
	cin >> n;
	long long  a[n];
	for(i = 0; i < n;i++){
		cin >> x;
		a[x] = i;
	}
	cin >> m;
	for(i = 0; i < m; i++){
		cin >> x;
		c = c + a[x] + 1;
		s = s + n - a[x];	
	}
	cout << c << ' ' << s; return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться