Решение задачи "Сбор посылок" с Codeforces

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


На складе есть робот и n посылок, которые он хочет собрать. Склад можно представить в виде координатной сетки. Изначально робот находится в точке (0,0). i-я посылка находится в точке (xi,yi). Гарантируется, что в одной точке не могут находиться две посылки. Также гарантируется, что в точке (0,0) посылки нет.

Робот наполовину сломан и может передвигаться только вверх ('U') и вправо ('R'). Другими словами, за один шаг робот может переместиться из точки (x,y) в точку (x+1,y) или в точку (x,y+1). Как сказано выше, робот хочет собрать все n посылок (в любом порядке). Он хочет сделать это за минимально возможное число шагов. Если существует несколько подходящих последовательностей шагов, робот хочет выбрать лексикографически минимальный путь.

Строка s длины n лексикографически меньше, чем строка t длины n если существует такой индекс 1≤j≤n, что для всех i от 1 до j−1 si=ti и sj

Код

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,t,i,v,u;
	cin>>t;
	while(t--){
	pair<int,int > a[1000];
	cin>>n;
	for(i=0;i<n;i++)
	cin>>a[i].first>>a[i].second;
	sort(a,a+n);
	int x=0,y=0,f=0;
	string ans="";
	for(i=0;i<n;i++)
	{
		int u=a[i].first,v=a[i].second;
		if(v<y)
		{	f=1;
			cout<<"NO\n";
			break;
		}
		ans+=string(u-x,'R');
		ans+=string(v-y,'U');
		x=u;
		y=v;
	}
	if(!f)
	cout<<"YES\n"<<ans<<endl;}
	
}

         

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


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

Комментарии

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