Решение задачи Утраченное настроение прошлого с Codeforces

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


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

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

Необходимая последовательность a имеет длину n. Утерянные элементы в ней сейчас заменены нулями. У Каики есть еще одна последовательность b, длина которой k равна числу утерянных элементов в a (т.е. числу нулей). Хитаги должна заменить каждый ноль в a одним элементом из b так, что каждый элемент из b будет использован ровно один раз. Хитаги, однако, знает, что, кроме 0, ни одно число не встречается суммарно в a и b более одного раза.

Если получившаяся последовательность не является возрастающей, то она позволит вернуть Хитаги вес. Вам предстоит определить, возможно ли такое. Другими словами, вы должны определить, возможно ли заменить каждый ноль в последовательности a числом из последовательности b так, чтобы каждое число из b было использовано ровно единожды, и получившаяся последовательность не являлась возрастающей.

Код

#include<bits/stdc++.h>
using namespace std;
int n,k,a[200],b[200],j;
bool f;
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<k;i++)
		cin>>b[i];
	for(int i=0;i<n;i++)
	{
		if(a[i]==0)
		{
			a[i]=b[j];
			j++;
		}
	}
	for(int i=1;i<n;i++)
		if(a[i]<a[i-1])
			f=1;
	if(k==1&&!f)
		cout<<"NO";
	else
		cout<<"YES";
	return 0;	
}

         

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



Комментарии

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