CF-1294-B Collecting Packages

2930 단어 문제 집
Codeforces Round #615 (Div. 3) 
CF-1294-B Collecting Packages_第1张图片
전송 문:http://codeforces.com/contest/1294/problem/B 
테스트 샘플:
input
3
5
1 3
1 2
3 3
5 5
4 3
2
1 0
0 1
1
4 3

output
YES
RUUURRRRUU
NO
YES
RRRRUUU

Note
For the first test case in the example the optimal path RUUURRRRUU is shown below:
CF-1294-B Collecting Packages_第2张图片
제목: 로봇 은 (0, 0) 위치 에 n 개의 좌표 가 n 개의 소포 가 존재 하고 로봇 은 위로 (U) 또는 오른쪽으로 (R) 만 이동 할 수 있다.t 개의 테스트 샘플 을 지정 합 니 다. 모든 테스트 샘플 은 n 과 n 개의 좌 표를 포함 합 니 다. 로봇 은 모든 n 개의 가방 을 수집 하고 싶 습 니 다.
사고방식: 만약 에 임의의 두 개의 점 과 한 개의 점 이 다른 점 의 왼쪽 상단 에 존재 한다 면 모든 가방 을 수집 할 수 없다. 그렇지 않 으 면 된다.모든 좌 표를 x, y 를 작은 것 에서 큰 것 으로 정렬 하고 순서대로 옮 겨 다 니 면 됩 니 다.
AC 코드:
#include
using namespace std;
struct Node
{
    int x,y;
}p[1005];
bool cmp(struct Node a,struct Node b)
{
    if(a.x==b.x)
        return a.yp[j].y)
                {
                    flag=1;
                    break;
                }
            if(flag)
                break;
        }
        if(flag)
        {
            printf("NO
"); continue; } else { printf("YES
"); for(int i=0;i

AC 코드 2 (최적화):
만약 에 임의의 두 개의 점 이 다른 점 왼쪽 상단 에 존재 한다 면 반드시 앞의 점 이 뒤의 점 의 왼쪽 상단 에 있 을 것 이다.이중 for 를 1 중 으로 최적화 하고 O (n ^ 2) 를 O (n) 로 변경 합 니 다.
#include
using namespace std;
struct Node
{
    int x,y;
}p[1005];
bool cmp(Node a,Node b)
{
    if(a.x==b.x)
        return a.yp[i].y)
            {
                flag=1;
                break;
            }
        }
        if(flag)
        {
            printf("NO
"); continue; } else { printf("YES
"); int x=0,y=0; for(int i=0;i

좋은 웹페이지 즐겨찾기