Решение задачи Сбалансированный тоннель с Codeforces

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


Рассмотрим тоннель на односторонней дороге. В течение некоторого дня n машин, пронумерованных от 1 до n, въехали в тоннель и выехали из него ровно по одному разу. Все машины ехали через тоннель с постоянными скоростями.

На въезде в тоннель установлена камера безопасности дорожного движения. Ещё одна такая же камера установлена на выезде из тоннеля. Идеальный баланс.

Благодаря камерам известно, в каком порядке машины въезжали в тоннель и выезжали из него. Никакие две машины не въезжали и не выезжали одновременно.

Правила дорожного движения запрещают обгоны внутри тоннеля. Если машина i обгоняет машину j внутри тоннеля, машина i должна быть оштрафована. Тем не менее, каждая машина может быть оштрафована не более одного раза.

Если говорить формально, то пусть машина i точно обогнала машину j, если машина i въехала в тоннель позже машины j, а выехала из тоннеля раньше машины j. Тогда машина i должна быть оштрафована тогда и только тогда, когда она точно обогнала хотя бы одну другую машину.

Определите, сколько машин следует оштрафовать.

Код

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 7;

int a[N], b[N], n;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++) {
		int t;
		cin >> t;
		b[t] = i;
	}
	int mx = b[a[1]];
	int res = 0;
	for (int i = 2; i <= n; i++) {
		if (mx > b[a[i]])
			res++;
		mx = max(mx, b[a[i]]);
	}
	cout << res;

	return 0;
}

         

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



Комментарии

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