题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1051

题目描述

There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:

(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l’ and weight w’ if l<=l’ and w<=w’. Otherwise, it will need 1 minute for setup.

You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are (4,9), (5,2), (2,1), (3,5), and (1,4), then the minimum setup time should be 2 minutes since there is a sequence of pairs (1,4), (3,5), (4,9), (2,1), (5,2).

思路

贪心算法,先对木棍长度进行排序,长度相同对重量进行排序。

然后求出符合要求的木棍序列并标记,对于不满足的木棍放到一边,下次总时间+1并在不满足的木棍中求出符合要求的木棍序列。

例如样例1,排序后

(1,4), (2,1), (3,5), (4,9), (5,2)

那么第一轮得到的满足要求的序列是(1,4), (3,5), (4, 9)

第二轮,从(2,1)开始,得到的满足要求的序列是(2,1), (5,2)

所以一共两次启动时间,答案为2。

AC代码

/*************************************************************************
    > File Name: 1051.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Mon 08 Jun 2015 04:27:41 PM CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
struct Wood {
    int l, w;
    bool mark;
} wood[5005];

bool cmp(const Wood &a, const Wood &b) { // 对木棍长度进行排序(升序),长度相同对重量进行排序(升序)。
    if(a.l == b.l)
        return a.w<b.w;
    return a.l < b.l;
}

int main()
{
#ifdef Oj
    freopen("1051.in", "r", stdin);
#endif
    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> wood[i].l >> wood[i].w;
            wood[i].mark=false;
        }
        int setup = 0;
        int pl, pw;
        sort(wood, wood+n, cmp); // 排序
        for(int i=0; i<n; ++i) { // 从第1个木棍开始
            if(!wood[i].mark) {  // 未被标记
                ++setup; // 总时间+1
                pl = wood[i].l; // 更新前一个木棍长度
                pw = wood[i].w; // 更新前一个木棍重量
                wood[i].mark = true; // 标记
            }
            for(int j=i+1; j<n; ++j) { // 从第i+1个木棍开始搜索
                if(!wood[j].mark && wood[j].l >= pl && wood[j].w >= pw) { // 如果符合要求
                    wood[j].mark = true; // 标记
                    pl = wood[j].l; // 更新前一个木棍长度
                    pw = wood[j].w; // 更新前一个木棍重量
                }
            }
        }
        cout << setup << endl;
    }
    return 0;
}