贪心 G - Wooden Sticks

G - Wooden Sticks

题目链接：HDU1051

题解

思路

题目要求给出所需的最短时间。
已知任意一个不满足比上一个更长更重的木棒都会使得加工时间增加一分钟，那么我们就要把木棒分成若干堆，其中任意一个堆的木棒都满足比上一个更重更长。这样堆的数量就是加工时间。

实现

实际上，并不需要完全模拟上述过程，只需要对木棒进行以长度为第一关键字，以重量为第二关键字的升序排序即可。
建立访问数组vis，表示当前木棒是否加工过。
对于每一个木棒，遍历地寻找比它更长更重的木棒，直到遍历完成，开始下一个木棒。
每开始一个木棒，时间加一。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>

using namespace std;
//#pragma GCC optimize(2)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ull unsigned long long
#define ll long long
#define rep(i, x, y) for(int i=x;i<=y;i++)
#define mms(x, n) memset(x, n, sizeof(x))
#define mmc(a, b) memcpy(a, b, sizeof(b))
#define INF (0x3f3f3f3f)
#define mod (ull)(1e9+7)
typedef pair<int, int> P;

namespace FastIO {
    const int bufsiz = 1 << 22;
    char buf[bufsiz];

    inline char getch() {
        static int tot;
        tot++;
        if (tot == bufsiz) {
            fread(buf, 1, bufsiz, stdin);
            tot = 0;
        }
        return buf[tot];
    }

    inline int read() {
        int x = 0;
        char c = getch();
        while (!isdigit(c))c = getch();
        while (isdigit(c))x = x * 10 + c - '0', c = getch();
        return x;
    }
}
using FastIO::read;
// length weight
vector<P> v(5010);
int vis[5010];

bool cmp(const P &a, const P &b) {
    if (a.first < b.first) return true;
    else return a.first == b.first && a.second <= b.second;
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int T = read();
//    scanf("%d", &T);
    while (T--) {
        mms(vis, 0);
        int x = read();
        rep(i, 1, x) {
            v[i].first = read();
            v[i].second = read();
        }
        sort(v.begin() + 1, v.begin() + x + 1, cmp);
        int ans = 1;
        int l, w;
        vis[1] = 1;
        rep(i, 1, x) {
            if (i == 1) l = v[1].first, w = v[1].second;
            else if (vis[i] == 0) {
                l = v[i].first, w = v[i].second;
                ans++;
            } else if (vis[i] == 1) continue;
            rep(j, i + 1, x) {
                if (vis[j]) continue;
                if (l <= v[j].first && w <= v[j].second) {
                    l = v[j].first, w = v[j].second;
                    vis[j] = 1;
                }
            }
        }
        printf("%d\n", ans);
    }
}