hdoj 1051 poj 1065 Wooden Sticks 【贪心】

以你之姓@ 2022-08-04 11:55 116阅读 0赞

# Wooden Sticks #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 15103    Accepted Submission(s): 6194**  
  
题目大意：有个木材加工机器，第一个放入的木材要花1分钟加工，若接下来放入的木材的长度和重量都大于等于前一个放入的木材，则这个木材加工花费的时间为零，否则得花费一分钟时间来加工；以此类推..........直到木材加工完为止；

首先给个数t，代表测试样例个数；

每个样例的第一行输入一个整数n，表示有n根木头，接下来的一行有

n对数（L,W），L为木材长度，W为木材重量；

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

思路：

因为题目中没说输入的木材是按长度从小到大（从大到小）排的，或是按重量从小到大（从大到小）排的，所以要先对木材进行排序，笔者是按木材长度从小到大排的（如果长度相同，则质量小的排前面）；然后就可以比较了，先定义两个变量来存放前一个木材的规格，再定义一个数组vis，1表示该木材已经加工，0反之，然后与后一个作比较，情况如下（注意，还得定义一个变量total来记录已加工的木材的总数）：

①若符合不花费时间的标准，就加工（即把对应的vis标为1）；

②若不符合标准就跳过，等待下一轮的加工；

③当total==n时，break；

已Accept代码

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int v[10001];						//记录序列号对应的木材是否已加工，已加工用1表示，没加工则用0表示； 
    
    struct ak{
        int l,w;
    }a[10001];
    
    int cmp(ak x,ak y){					//排序 
        if(x.l<y.l)						//短的排前面 
            return 1;
        else if(x.l==y.l)				//如果一样长 
            if(x.w<y.w)					//轻的排前面 
                return 1;
        return 0;
    }
    
    int main(){
        int t,n,i,j;
        scanf("%d",&t);
        while(t--){
            memset(v,0,sizeof(v));
            scanf("%d",&n);
            a[0].l=0;
            a[0].w=0;
            for(i=1;i<=n;i++)
                scanf("%d%d",&a[i].l,&a[i].w);
            sort(a,a+n+1,cmp);			//排序 
            int time=1,s=0;				//time记录花费的时间，s记录有多少木材已加工 
            int c=a[0].l,z=a[0].w;
            v[0]=1;
            while(s!=n){				//当已加工木材的数量为n时，循环结束 
                for(i=0;v[i]!=0;i++);
                c=a[i].l;
                z=a[i].w;
                for(i=1;i<=n;i++){
                    if(a[i].l>=c&&a[i].w>=z&&!v[i]){		//判定是否符合不花时间的标准 
                        c=a[i].l;							//符合标准就对前一个木材的规格进行更新 
                        z=a[i].w;
                        v[i]=1;						//把该木材标记为已加工 
                        s++;						//然后把已加工木材数加一； 
                    }
                }
                if(s!=n)							//如果本次循环完了，而还有木材没有加工，则所花时间加一 
                    time++;
            }
            printf("%d\n",time);
        }
        return 0;
    }