ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[杭电多校3 | HDUOJ7170]Package Delivery(贪心 + 优先队列)

2022年8月3日 112点热度 0人点赞 0条评论

题目传送门:Problem - 7170 (hdu.edu.cn)

题意 / Problem

有N个包裹,可以在[l, r]的时间内去取,一次最多取k个,问最少取多少次可以取完所有包裹。

思路 / Thought

贪心的思想,确实很难想,但是题目做多了也容易想到,区间先排序。

将区间分两种方法排序,a数组根据r排序,b数组根据排序。

为使得取包裹次数尽可能少,就应该每次取包裹时间尽可能晚(因为这样可以使得每次取得的包裹尽可能达到k个),但是又一定要取到第一个包裹,所以每次取r最小的那个包裹(从前往后遍历a数组),并且在b数组中将l <= 最小的r的所有包裹都加入到队列里(注意只有b数组的元素入队),然后从队列中取出r最小的k个包裹,并标记为已经取走了,往下遍历a时遇到取走的就跳过。

这里可能会遇到一个问题:每次从队列中取走k个,有没有可能队列里还剩下一些包裹,后面会取不出来呢?不会的,因为a数组会遍历完,最坏的情况就是每次取一个,按照a中的顺序取。

利用双指针和优先队列可以完成以上操作。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int maxn = 1e5 + 9, MAXL = 55;
int N, K;

struct Node
{
	int l, r, id;
}a[maxn], b[maxn];
bitset<maxn> del;
bool cmpl(Node &u, Node &v){return u.l < v.l;}
bool cmpr(Node &u, Node &v){return u.r < v.r;}

struct cmp
{
	bool operator ()(const PII &a, const PII &b)const
	{
		return a.first > b.first;
	}
};

void solve()
{
	del.reset();
	cin >> N >> K;
	for(int i = 1;i <= N; ++ i)
	{
		cin >> a[i].l >> a[i].r;
		a[i].id = i;
		b[i] = a[i];
	}
	sort(a + 1,a + 1 + N, cmpr);
	sort(b + 1,b + 1 + N, cmpl);
	priority_queue<PII, vector<PII>, cmp> pq;
	
	int ans = 0;
	for(int i = 1, j = 1;i <= N; ++ i)//每次选择r最小的 
	{
		if(del[a[i].id])continue;//如果已经拿走了就跳过
		 
		while(j <= N && b[j].l <= a[i].r)//将可以拿走的都放到队列里 
		{
			pq.push({b[j].r, b[j].id});
			++ j;
		}
		ans ++;
		for(int t = 1;t <= K && !pq.empty(); ++ t)//每次选 r 最小的 k 个拿走 
		{
			del[pq.top().second] = true;
			pq.pop();
		}
	}
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	int _;cin >> _;
	while(_ --)solve();
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ hduoj 优先队列 双指针 算法竞赛 贪心
最后更新:2022年8月3日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题意 / Problem
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号