HDU 1051 Wooden Sticks

原题传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1051

 

 

Wooden Sticks

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11290    Accepted Submission(s): 4642

Problem Description

 

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).

 

 

Input

 

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1<=n<=5000, that represents the number of wooden sticks in the test case, and the second line contains n 2 positive integers l1, w1, l2, w2, ..., ln, wn, each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.

 

 

Output

 

The output should contain the minimum setup time in minutes, one per line.

 

 

Sample Input

3 5 4 9 5 2 2 1 3 5 1 4 3 2 2 1 1 2 2 3 1 3 2 2 3 1

 

 

Sample Output

2 1 3

 

 

Source

 

Asia 2001, Taejon (South Korea)

 

 

 

Recommend

 

We have carefully selected several similar problems for you:  1050 1052 1045 1053 1789

 

分析：这是一道明显的区间选择问题的贪心算法题，这里提供两种思路。

思路一：定义一个结构体

struct Stick{

   int  len; int wei; int flag }

用一个结构体数组Stick[MAXN]，把所有木棍存入这个数组内，然后进行以wei降序排序，排完序后，然后循环扫描这个数组，每第一次扫描到未标记的(所有木棍初始化的时候都未标记)，就把当前木棍的len取出来存入current中，然后遍历完整个数组，把扫描到未标记的木棍的len取出，如果小于current，那么就将它标记flag = 1;current  = 取出的len，这样就可以把所有能够在不重置时间的木棍在每一次遍历数组的时候选出来。当标记木棍数量达到所有木棍数量的时候就完成了，那么遍历数组的次数就是最小时间。

这样说太抽象了，我们以第一个测试数据为例（已经以wei排好序）

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

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

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

total step is 2;

思路二：同样定义一个结构体，不过不需要flag;

struct Stick{

   int  len; int wei; }

这里我们用优先队列和队列来存储所有木棍，首先把所有木棍存入以wei降序排序的优先队列中，然后把优先队列中的数据拷贝到普通队列中，把第一个数据pop（）出来，current =  第一个木棍.len ；while(队列不等于空)，我们每次都去取出队头元素，如果它的len<=current，那么current = 它的len ，如果不符合它的len<=current，把它重新压入队尾，等待第二次pop（）;也是每遍历一次队列所有元素，时间+1，那么怎么来控制和识别遍历过所有元素呢，可以用visit  来记录所访问过的stick，用left来记录你需要遍历的队列元素个数，用choose来记录你从队列彻底选择出来的stick数量，一直到队列为空。

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

step1:选出(4,9)  (3,5)  (1,4)  队列剩下： (5,2)  (2,1)

step2：选出  (5,2)  (2,1) 队列为空

//最少区间问题 贪心 HDU 1051
#include<cstdio>
#include<queue>
using namespace std;
struct Stick{
    int len;
    int wei;
    bool operator <(const Stick &rhs) const{
        return this->wei <= rhs.wei;
    }
};
priority_queue<Stick> qs;
queue<Stick> s;
int T,n,len,wei,count,visit,left,choose;
Stick curs,temp;
int main(){
    scanf("%d",&T);
    while(T--){
        choose = 0;
        visit = 0;
        count = 1;
        scanf("%d",&n);
        left = n;
        //让优先队列，以weight值降序排列结构体
        for(int i=0;i<n;i++){
            scanf("%d%d",&len,&wei);
            Stick st;
            st.len = len;
            st.wei = wei;
            qs.push(st);
        }
        //将优先队列的元素全部转移到普通队列中
        while(!qs.empty()){
          s.push(qs.top());
          qs.pop();
        }
        //取最大区间
        curs = s.front();
        s.pop();
        visit++;
        choose++;
        //一直到取完所有stick为止
        while(!s.empty()){
            //如果遍历过一次队列说明已经找所有不需要重新建立时间的stick
            if(visit == left){
                count++;
                left = left - choose;
                curs = s.front();
                s.pop();
                choose = 1;
                visit = 1;
            }
            //如果队列为空说明已经全部选出来了
            if(s.empty())
                break;
            temp = s.front();
            s.pop();
            visit++;

            //如何符合不用重新设置时间的，那么选出来
            if(curs.len >= temp.len ){
                curs = temp;
                choose++;
            }else{
                //否则继续推送到队列里等待下次选集
                s.push(temp);
            }
        }
        printf("%d\n",count);
    }
    return 0;
}