典型的贪心算法，和前面1029一样也是工作时间调度问题。
复制代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXSIZE = 5000;
struct stick
{//木条
int length;//长度
int width;//宽度
bool isVisited;
}Sticks[MAXSIZE];
bool lessThan(const stick& s1,const stick& s2)
{//按木条长度从大到小排序
return s1.length<s2.length;
}
int main(void)
{
int cases,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);//排序
//贪心法
int length,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;
}
return 0;
}
复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2008/10/29/1321967.html，如需转载请自行联系原作者
