Coder Space

题意：在一个矩形区域内,机器人从左上角出发,每次只能沿着现在位置的下方和右方移动,在移动过程中收拾垃圾,一直到区域的右下角,现在给出所有垃圾的位置，
            求解最少需要多少个机器人才能将这些垃圾清理成功.

解法：对于位置(x1,y1)和位置(x1,y2)处的垃圾,如果满足x1<=x2&&y1<=y2(当然不可能出现两个相同的坐标),那么这两个位置处的垃圾只需要一个机器人就可以成功
            处理，则有Dilworth定理可知,将x坐标升序排序，相等时将y坐标升序排序(实际上题目就是按照这种形式输入),然后对y序列求解最长递减子序列数目即为所求。
            贪心算法可求。同1065。

源代码
 1#include<iostream>
 2#include<algorithm>
 3
 4using namespace std;
 5
 6const int MAXN = 580;
 7
 8struct Garbage
 9{
10    int r;
11    int c;
12    bool visited;
13};
14
15Garbage gar[MAXN];
16
17bool com(Garbage s1, Garbage s2)                //比较函数
18{
19    if(s1.r == s2.r)
20    {
21        return s1.c < s2.c;
22    }
23    else
24    {
25        return s1.r < s2.r;
26    }
27}
28
29int main()
30{
31    int minR;
32    Garbage cur;
33    bool allVisited;
34    int ind;                             //当前序列的第一元素数组下标
35    int n;
36
37    cin>>gar[0].r>>gar[0].c;
38    while(!(gar[0].r == -1 && gar[0].c == -1))
39    {
40        gar[0].visited = false;
41        n = 0;
42        while(!(gar[n].r == 0 && gar[n].c == 0))
43        {
44            ++n;
45            cin>>gar[n].r>>gar[n].c;
46            gar[n].visited = false;
47        }
48        ++n;
49
50        sort(gar,gar+n,com);             //排序
51
52        minR = 0;
53        ind = 0;
54        allVisited = false;
55        while(!allVisited)
56        {
57            allVisited = true;
58            for(;ind<n; ind++)           //新序列
59            {
60                if(!gar[ind].visited)
61                {
62                    cur = gar[ind];
63                    gar[ind].visited = true;
64                    allVisited = false;
65                    ++minR;
66                    break;
67                }
68            }
69            for(int j=ind+1; j<n; j++) 
70            {
71                if(!gar[j].visited && cur.r <= gar[j].r && cur.c <= gar[j].c)
72                {
73                    cur = gar[j];
74                    gar[j].visited = true;
75                }
76            }
77        }
78        cout<<minR<<endl;
79        cin>>gar[0].r>>gar[0].c;
80    }
81    return 0;
82}