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

发布于 2022-03-27  673 次阅读


题目链接: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09