典型的贪心算法,和前面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;
}
分享到:
相关推荐
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
一个非常非常非常非常实用的zoj结题代码
zoj 1003 c语言的,要写这么多描述吗。。
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
ZOJ1805代码
zoj1027解题指南和代码,还不错,是学校培训给的。
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm
zoj4041正确题解源代码,以及运行程序
zoj吐血制作,希望大家喜欢
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
能AC 通过的c++代码,包括zoj1002,1091,1789
zoj 1002 C语言的为什么描述要这么多字啊。。