CodeForces 1294B Collecting Packages(排序+贪心)

 

http://codeforces.com/contest/1294/problem/B

CodeForces 1294B Collecting Packages(排序+贪心)

 

 CodeForces 1294B Collecting Packages(排序+贪心)

 

 CodeForces 1294B Collecting Packages(排序+贪心)

 

 大致题意:

一张图上有n个包裹,给出他们的坐标,一个机器人从(0,0)出发,只能向右(R)或向上(U),问能否收集到所有包裹,如果能,给出字典序最小的路径。

 

最开始当成搜索题了,其实可以排序+贪心写的。

 

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 const int maxn=1e5+10;
17 using namespace std;
18  
19 pair<int,int> p[1005];
20  
21 int main()
22 {
23     #ifdef DEBUG
24     freopen("sample.txt","r",stdin);
25     #endif
26 //    ios_base::sync_with_stdio(false);
27 //    cin.tie(NULL);
28     
29     int T;
30     scanf("%d",&T);
31     while(T--)
32     {
33         int n;
34         scanf("%d",&n);
35         for(int i=1;i<=n;i++)
36         {
37             scanf("%d %d",&p[i].first,&p[i].second);
38         }
39         sort(p+1,p+1+n);
40         string ans;
41         int X,Y;
42         X=Y=0;
43         int flag=1;
44         for(int i=1;i<=n;i++)
45         {
46             for(int j=X;j<p[i].first;j++)
47                 ans+='R';
48             X=p[i].first;
49             if(p[i].second<Y)
50             {
51                 flag=0;break;
52             }
53             else
54             {
55                 for(int j=Y;j<p[i].second;j++)
56                     ans+='U';
57                 Y=p[i].second;
58             }
59         }
60         if(!flag) printf("NO\n");
61         else 
62         {
63             printf("YES\n");
64             cout<<ans<<endl;
65         }
66     }
67     
68     return 0;
69 }

 

 

 

 

 

 

 

 

 

 

 

 

 

 

-

上一篇:Codeforces Round #615 (Div. 3) B Collecting Packages


下一篇:[ARC083]Collecting Balls