提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

贪心算法WOODENSTICKS实例代码

实例算法代码 贪心
2023-06-13 09:15:00 时间

ProblemDescription
Thereisapileofnwoodensticks.Thelengthandweightofeachstickareknowninadvance.Thesticksaretobeprocessedbyawoodworkingmachineinonebyonefashion.Itneedssometime,calledsetuptime,forthemachinetoprepareprocessingastick.Thesetuptimesareassociatedwithcleaningoperationsandchangingtoolsandshapesinthemachine.Thesetuptimesofthewoodworkingmachinearegivenasfollows:
(a)Thesetuptimeforthefirstwoodenstickis1minute.(b)Rightafterprocessingastickoflengthlandweightw,themachinewillneednosetuptimeforastickoflengthl"andweightw"ifl<=l"andw<=w".Otherwise,itwillneed1minuteforsetup.
Youaretofindtheminimumsetuptimetoprocessagivenpileofnwoodensticks.Forexample,ifyouhavefivestickswhosepairsoflengthandweightare(4,9),(5,2),(2,1),(3,5),and(1,4),thentheminimumsetuptimeshouldbe2minutessincethereisasequenceofpairs(1,4),(3,5),(4,9),(2,1),(5,2).

Input
TheinputconsistsofTtestcases.Thenumberoftestcases(T)isgiveninthefirstlineoftheinputfile.Eachtestcaseconsistsoftwolines:Thefirstlinehasanintegern,1<=n<=5000,thatrepresentsthenumberofwoodensticksinthetestcase,andthesecondlinecontainsn2positiveintegersl1,w1,l2,w2,...,ln,wn,eachofmagnitudeatmost10000,whereliandwiarethelengthandweightoftheithwoodenstick,respectively.The2nintegersaredelimitedbyoneormorespaces.

Output
Theoutputshouldcontaintheminimumsetuptimeinminutes,oneperline.

SampleInput
35495221351432211223132231

SampleOutput
213

复制代码代码如下:


#include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 #defineN5000;

 structnode
 {
    intl;
    intw;
    intflag;
 }sticks[5000];
 intcmp(constvoid*p,constvoid*q)
 {
    structnode*a=(structnode*)p;
    structnode*b=(structnode*)q;
    if(a->l>b->l)return1;
    elseif(a->l<b->l)return-1;
    elsereturna->w>b->w?1:-1;
 }
 intmain()
 {
    intt,n,cnt,cl,cw;
    inti,j;
    scanf("%d",&t);
    while(t--)
    {
        memset(sticks,0,sizeof(sticks));
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d%d",&sticks[i].l,&sticks[i].w);
        qsort(sticks,n,sizeof(sticks[0]),cmp);
        sticks[0].flag=1;
        cl=sticks[0].l;
        cw=sticks[0].w;
        cnt=1;
        for(j=1;j<n;j++)
        {
            for(i=j;i<n;i++)
            {
                if(!sticks[i].flag&&sticks[i].l>=cl&&sticks[i].w>=cw)
                {
                    cl=sticks[i].l;
                    cw=sticks[i].w;
                    sticks[i].flag=1;
                }
            }
            i=1;
            while(sticks[i].flag)
               i++;
            j=i;
            if(j==n)break;
            cl=sticks[j].l;
            cw=sticks[j].w;
            sticks[j].flag=1;
            cnt++;
        }
        printf("%d\n",cnt);

    }
    return0;
 }

题意：

我们要处理一些木棍，第一根的时间是1分钟，另外的，在长度为l，重为w的木棍后面的那根的长度为l",重量w"，只要l<=l"并且w<=w"，就不需要时间，否则需要1分钟，求如何安排处理木棍的顺序，才能使花的时间最少。

思路：

贪心算法。先把这些木棍按长度和重量都从小到大的顺序排列。cl和cw是第一根的长度和重量，依次比较后面的是不是比当前的cl，cw大，是的话把标志flag设为1，并跟新cl,cw。比较完后，再从前往后扫描，找到第一个标志位为0的，作为是第二批的最小的一根，计数器加一。把它的长度和重量作为当前的cl，cw，再循环往后比较。直到所有的都处理了。

相关文章