Решение задачи Вася и книги с Codeforces

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


У Васи есть n книг, пронумерованных от 1 до n, сложенных в стопку. Самая верхняя книга имеет номер a1, следующая за ней имеет номер a2, и так далее. Самая нижняя книга имеет номер an. Все книги имеют различные номера.

Вася хочет переложить все книги в рюкзак за n шагов. На i-м шаге он хочет переложить в рюкзак книгу с номером bi. Если книга с номером bi есть в стопке — он перекладывает эту книгу и все книги, лежащие над книгой bi, иначе переходит к следующему шагу. Например, если книги лежат в порядке [1,2,3] (книга 1 лежит наверху), а Вася перекладывает книги в порядке [2,1,3], то на первом шаге он переложит две книги (с номерами 1 и 2), на втором — ни одной (так как книги 1 уже нет в стопке), а на третьем — одну (с номером 3). Обратите внимание, что числа b1,b2,…,bn различны.

Помогите Васе! Сообщите ему, сколько книг он переложит в рюкзак на каждом шаге.

Код

#include<bits/stdc++.h>
using namespace std;
int n,a[200005],b[200005],c[200005],s,t;
int main()
{
	cin>>n;
	for(int i = 1; i <= n;i++){
		scanf ("%d",&a[i]);
		c[a[i]] = i;
	}
	for(int i = 1; i <= n; i++){
		scanf ("%d", &b[i]);
		t = max(0,c[b[i]]-s);
		printf("%d ",t);
		s += t;
	}
	return 0;
}

         

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



Комментарии

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