HDU 1051 Wooden Sticks（贪心）

November 30, 2015

题目链接

题意：第一行 T 组数据，每组数据的第一行 n 代表有 n 个棍子，接下来 n 行每行两个数，代表这个棍子的长度和重量。一个机器来加工这些棍子，如果加工的第二根棍子的长和重量都不小于第一根的，那么就不需要机器的启动时间，否则需要 1 的启动时间。问加工这些棍子需要最小的启动时间。

题解：定义结构体，存储每个棍子的长和重量，还有一个 flag 变量来存储这个棍子是否被访问过。按照长从小到大排序，长度相等时按照重量从小到大排序。排好之后遍历。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

struct node{
    int a, b;
    bool flag;
}N[5005];

int cmp(node x, node y){
    if(x.a == y.a)
        return x.b < y.b;
    else
        return x.a < y.a;
}

int main(){
    //freopen("a.txt", "r", stdin);
    int T, n;
    cin >> T;
    while(T--){
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            scanf("%d %d", &N[i].a, &N[i].b);
            N[i].flag = 0;
        }
        sort(N, N+n, cmp);
        int ans = n;
        for(int i = 0; i < n; i++){
            if(N[i].flag)
               continue;
            int a1 = N[i].a;
            int b1 = N[i].b;
            for(int j = i+1; j < n; j++){
                if(N[j].a >= a1 && N[j].b >= b1 && !N[j].flag){
                    ans--;
                    N[j].flag = 1;
                    a1 = N[j].a;
                    b1 = N[j].b;
                }
            }
        }
        printf("%dn", ans);
    }
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]