1. 云栖社区>
  2. >
  3. 正文

1008 加工木棍问题

作者:用户 来源:互联网 时间:2018-08-31 11:19:08

贪心算法

1008 加工木棍问题 - 摘要: 本文讲的是1008 加工木棍问题, 简单题意:  有一堆n木棍。每个棍子的长度和重量都提前知道。棒是由木工机床在加工一个接一个时尚。它需要一些时间,启动时间,呼吁机器准备处理一根棍子。设置时间与清洁有关操作和改变机器

简单题意: 

有一堆n木棍。每个棍子的长度和重量都提前知道。棒是由木工机床在加工一个接一个时尚。它需要一些时间,启动时间,呼吁机器准备处理一根棍子。设置时间与清洁有关操作和改变机器的工具和形状。给出了木工机床的安装时间如下:

(一)设置第一根木棍是1分钟的时间。

(b)后加工一根长度和重量w,机器将不需要设置时间一根长度和重量w '如果l < = l”和w < = w”。否则,它将需要1分钟的设置。

思路:

将其给的数据,先将其从大到小排序,再依次比较第二个值即可。

代码如下:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct club
{
	int x,y;
};
bool cmp (const club &k,const club&h)
{
	if(k.x<h.x) 
		return true;
	else
		if(k.x==h.x)
		return k.y<h.y ;
	return false;
}
int main()
{
	int b[10000];
	int m,n,sum=0,i,j,pp;
	club a[10000];
	cin>>m;
	while(m--)
	{
		cin>>n;
		for(i=1;i<=n;i++)
		{
			cin>>a[i].x >>a[i].y ;
		}
		memset(b,0,sizeof(b));
		sort(a+1,a+n+1,cmp);
                sum=0;
    	        for(i=1;i<=n;i++)
		{
                        if(b[i]==1)
                          continue;
			
			b[i]=1;
			sum++;
                        pp=a[i].y;
			for(j=i+1;j<=n;j++)//将第二个值比较
			{
				if(pp<=a[j].y&&b[j]==0)
				{
					pp =a[j].y ;
					b[j]=1;//若符合则将该数标记, 防止重复计算
				}
			}
		int kk=0;
                for(j=1;j<=n;j++)//判断是否所有的数都以被标记
                   if(b[j]==1)
                     kk++;
                if(kk==n)
                  break;
		}
		cout<<sum<<endl;
	}
}
感想: 此类问题比较简单的贪心问题,比较再标记即可。

ACID:00737746


以上是云栖社区小编为您精心准备的的内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索贪心算法 ,以便于您获取更多的相关知识。

弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率

40+云计算产品,6个月免费体验

现在注册,免费体验40+云产品,及域名优惠!

云服务器9.9元/月,大学必备