huring
0%

51nod-1890-方块塔

Posted on In

题目：
 地上有n个方块，每一个方块高度都是H，第i（1<=i<=n）个方块的长和宽分别为L[i],W[i]。

 现在开始堆方块塔，每次可以拿一个方块放到一个方块塔上，但是有一个要求，设当前塔顶的方块长度和宽度分别为Ltop,Wtop，当前拿到的方块长度和宽度分别为Lcur,Wcur，当满足Lcur<=Ltop&&Wcur<=Wtop的时候，这个方块才能被放到塔顶，并且取代之前的塔顶成为新塔顶。

 由于土地比较贵，所以想要堆出来的塔的数目尽可能少，请计算最少的塔的数目。

 例如，现在有5个方块，长度和宽度分别为：( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , ( 4 , 1 )。那么最少可以堆成两座塔：( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 )分为一堆；( 1 , 2 ) , ( 2 , 5 )分为一堆。

输入
 单组测试数据。
 第一行给出一个整数n （1 <= n <= 5000）。
 第二行有2*n个整数L[1] , W[1] , L[2] , W[2] ,…, L[n] , W[n]。（1<=L[i],W[i]<=10000）
输出
 输出一个整数，表示答案。
输入样例
 样例输入1
 5
 4 9 5 2 2 1 3 5 1 4
输出样例
 样例输出1
解法：
 按照w，l的大小进行排序，每次遍历全部，每一次遍历选出来一组符合条件的块，当所有方块被选出之后则结束，遍历的次数即为ans
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<algorithm>
using namespace std;
struct point
{
    int x,y;
};
point p[5010];
bool cmp(point a, point b)
{
    if(a.x != b.x)
        return a.x < b.x;
    else
    {
        return a.y < b.y;
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d%d",&p[i].x, &p[i].y);
    sort(p, p + n, cmp);
    //for(int i = 0; i< n; i++)
       // printf("%d %d\n",p[i].x,p[i].y);
    int ans = 0;
    bool flag = false;
    while(!flag)
    {
        flag = true;
        int nx=0, ny=0;
        for(int i = 0; i < n; i++)
        {
            if(p[i].x!=0 && p[i].y!=0)
            {
                flag = false;
                if(p[i].x >= nx && p[i].y >= ny){
                    nx = p[i].x;
                    ny = p[i].y;
                    p[i].x = 0;
                    p[i].y = 0;
                }
            }
        }
        ans++;
    }
    printf("%d\n", ans - 1);
    return 0;
}

ps:最近时间都很紧迫，今天差点放弃，幸亏1A了，否则现在的我已经放弃了。加油加油！！！