ErikTse Runtime

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

[ABC245]E - Wrapping Chocolate(multiset + 贪心)

2022年3月27日 597点热度 0人点赞 0条评论

题目链接:E - Wrapping Chocolate (atcoder.jp)

题目大意

有N个矩形巧克力,M个矩形盒子,一个盒子只能放最多一块巧克力,且巧克力的长和宽不能旋转,问能否装下。

思路

输入巧克力和盒子的数据,将巧克力的type设为1,盒子为0,将他们存在同一个数组里,数组大小为N + M。

将所有矩形(包括巧克力和盒子)按照宽度排降序,规则是宽更大的在左边,如果宽相同,则盒子在前,巧克力在后。

开一个序列S。

然后从左往右遍历整个数组,如果Ai是盒子就直接将长度L加入到序列S中去。

如果是巧克力,就在S中找是否存在盒子可以装下这个巧克力,所有可能的盒子都在S序列中已有的元素中,因为如果还没加进来说明宽度要比这个巧克力的宽度还要严格小。

但是如果用线性表显然不好操作,所以可以用multiset来优化复杂度,multiset的插入和删除操作的复杂度均为O(logN),十分强大。

结合multiset自带的lower_bound方法可以二分找到所需的盒子。

我的代码在排序时使用了lambda表达式,下面这篇文章有介绍:

C++11 lambda表达式精讲 (biancheng.net)

这里还有一道使用了multiset的题目,也使用了multiset的lower_bound方法,大伙儿可以对比学习。

D - Sequence Query(二分查找,set) (eriktse.com)

代码

/*Copyright (C) Eriktse 2022*/
#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int readInt()
{
	int s = 0,w = 1;char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
	while('0' <= ch && ch <= '9')s = s * 10 + ch - '0', ch = getchar();
	return s * w;
}

const int maxn = 2e5 + 10;
int N, M;

struct rec
{
	int w, l;
	bool t;//0盒子,1巧克力 
}A[maxn * 2];

multiset<int> ss;

signed main()
{
	cin >> N >> M;
	for(int i = 1;i <= N; ++ i)
	{
		A[i].w = readInt();
		A[i].t = 1;
	}
	for(int i = 1;i <= N; ++ i)A[i].l = readInt();
	
	for(int i = N + 1;i <= N + M; ++ i)
	{
		A[i].w = readInt();
		A[i].t = 0;
	}
	for(int i = N + 1;i <= N + M; ++ i)A[i].l = readInt();
	
	sort(A + 1, A + 1 + N + M, [](rec &a,rec &b)
	{
		if(a.w != b.w)return a.w > b.w;
		return a.t == 0 && b.t == 1;
	});
	bool ans = 1;
	for(int i = 1;i <= N + M; ++ i)
	{
		int w = A[i].w, l = A[i].l;
		bool t = A[i].t;
		
		if(t == 0)ss.insert(l);
		else
		{
			auto it = ss.lower_bound(l);
			if(it == ss.end())
			{
				ans = 0;
				break;
			}
			ss.erase(it);
		}
	}
	printf("%s\n",ans ? "Yes" : "No");
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: atcoder C++ multiset 二分 贪心
最后更新:2022年7月9日

Eriktse

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

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

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

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号