首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【HPUoj】Wooden Sticks(贪心)

【HPUoj】Wooden Sticks(贪心)

作者头像
FishWang
发布2025-08-27 12:09:48
发布2025-08-27 12:09:48
8800
代码可运行
举报
运行总次数:0
代码可运行

题目链接:点击打开链接

问题 F: Wooden Sticks

时间限制: 1 Sec 内存限制: 128 MB 提交: 1 解决: 1 状态

题目描述

Lialosiu要制作木棍,给n根作为原料的木棍的长度和重量。根据要求求出制作木棍的最短时间。

首先我们知道制作第一个木棍需要1分钟,若是接着要制作的木棍的重量和长度都不少于当前的木棍,那么就不需要建立的时间,若是没有,则再需要建立时间,也就是1分钟。

举个例子,如果你有五个原料木棍,他们的长度和重量分别是(4,9), (5,2), (2,1), (3,5), 和 (1,4), 那么第一分钟你要建立一根木棍作为起始参照,比如(1,4)接下来(3,5)和(4,9)都可以不花费时间,然后用第二分钟选取(2,1)这跟木棍作为参照,接下来(5,2)可以不花费任何时间,总的来说,你一共花费了两分钟,这也是你可能使用的最少时间。

现在给了n个木棍的长度和重量,你能求出使用这些木棍的最少时间吗?

输入

首先,输入一个正整数T ,代表有T组数据。

接下来,第二行你要输入正整数n(1<=n<=5000)代表的你的原料木棍个数。

第三行你要输入2*n 个 正整数l1, w1, l2, w2, ..., ln, wn,每一个数字都不超过10000 。 li代表第i根木棍的长度,wi代表第i根木棍的重量。

输出

输出一个整数,代表最少需要的时间t。

样例输入

代码语言:javascript
代码运行次数:0
运行
复制
3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1

样例输出

代码语言:javascript
代码运行次数:0
运行
复制
2
1
3

很简单的贪心,能接上就接,不能就跳过,然后再开始新的一轮。

代码如下:

代码语言:javascript
代码运行次数:0
运行
复制
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
#define PI acos(-1.0)
#define LL long long
struct node
{
	int l,w;
}t;
bool cmp(node a,node b)
{
	if (a.l == b.l)
		return a.w < b.w;
	return a.l < b.l;
}
int main()
{
	int u;
	int n;
	scanf ("%d",&u);
	while (u--)
	{
		scanf ("%d",&n);
		vector<node> d;
		for (int i = 1 ; i <= n ; i++)
		{
			scanf ("%d %d",&t.l,&t.w);
			d.push_back(t);
		}
		sort(d.begin(),d.end(),cmp);
		int ans = 0;
		while (!d.empty())
		{
			ans++;
			t = d[0];
			d.erase(d.begin());
			for (int i = 0 ; i < d.size() ; i++)
			{
				if (d[i].l >= t.l && d[i].w >= t.w)
				{
					t = d[i];
					d.erase(d.begin()+i);		//能接上就抹除 
					i--;
				}
			}
		}
		printf ("%d\n",ans);
	}
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-08-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题 F: Wooden Sticks
  • 题目描述
  • 输入
  • 输出
  • 样例输入
  • 样例输出
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档