`
phinecos
  • 浏览: 339905 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

ZOJ1025 Wooden Sticks

 
阅读更多

典型的贪心算法,和前面1029一样也是工作时间调度问题。

<!--<br /> <br /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br /> http://www.CodeHighlighter.com/<br /> <br /> -->#include<iostream>
#include
<vector>
#include
<algorithm>
usingnamespacestd;

constintMAXSIZE=5000;
structstick
{
//木条
intlength;//长度
intwidth;//宽度
boolisVisited;
}Sticks[MAXSIZE];

boollessThan(conststick&s1,conststick&s2)
{
//按木条长度从大到小排序
returns1.length<s2.length;
}
intmain(void)
{
intcases,i,j,k,n;
cin
>>cases;
for(i=1;i<=cases;++i)
{
cin
>>n;
vector
<stick>stickVect;
for(j=0;j<n;++j)
{
cin
>>Sticks[j].length>>Sticks[j].width;
Sticks[j].isVisited
=false;
stickVect.push_back(Sticks[j]);
}
sort(stickVect.begin(),stickVect.end(),lessThan);
//排序
//贪心法
intlength,width,time=0,count=0;
for(j=0;j<n;++j)
{
if(stickVect[j].isVisited==false)
{
//还未访问,作为新一轮的排头兵
time++;//新一轮了,时间加
length=stickVect[j].length;
width
=stickVect[j].width;
stickVect[j].isVisited
=true;
for(k=0;k<n;++k)
{
if(stickVect[k].isVisited==false)
{
if(stickVect[k].length>=length&&stickVect[k].width>=width)
{
//此木条可以和排头兵一起顺利通过
stickVect[k].isVisited=true;
length
=stickVect[k].length;
width
=stickVect[k].width;
}
}
}
}
}
cout
<<time<<endl;
}
return0;
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics