首页 > 其他分享 >[ABC245E] Wrapping Chocolate题解

[ABC245E] Wrapping Chocolate题解

时间:2023-03-18 17:11:14浏览次数:48  
标签:巧克力 盒子 int 题解 Wrapping Chocolate ABC245E

听说没人写,那就来一发。

这种偏序问题大概率是要排个序的。将盒子和巧克力视为一个东西,\(c\) 视为 \(a\),\(d\) 视为 \(b\),放在一起以 \(a\) 为第一关键字,\(b\) 为第二关键字降序排序。此时,我们发现前面的盒子的 \(a\) 值一定是满足后面巧克力的 \(b\) 值的。所以记录还没被用的所有盒子的 \(b\) 值,每次有巧克力就在其中找到其 \(b\) 值的后继,即最小的 \(b'\geq b\) 来装。这样一定是最优的。

再举一个具体一点的例子:

在这种情况下,如果两个盒子都满足,选择 \(2\) 仍然是更优的,因为 \(a\) 的条件两个都一定能满足,\(b\) 却不一定。

用一个 multiset 维护即可。还要注意排序的时候如果有同等大小的巧克力和盒子,盒子要排在前面。

code:

点击查看代码
int n,m;
struct node{
	int x,y,op;
}e[N<<1];
multiset<int> st;
void solve(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&e[i].x);
		e[i].op=1;//要记录是盒子还是巧克力
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&e[i].y);
	}
	for(int i=n+1;i<=n+m;i++){
		scanf("%d",&e[i].x);
	}
	for(int i=n+1;i<=n+m;i++){
		scanf("%d",&e[i].y);
	}
	sort(e+1,e+n+m+1,[&](node a,node b){return a.x!=b.x?a.x>b.x:(a.y!=b.y?a.y>b.y:a.op<b.op);});
	for(int i=1;i<=n+m;i++){
		if(e[i].op){
			auto it=st.lower_bound(e[i].y);
			if(it==st.end()){
				puts("No");
				return;
			}
			st.erase(it);
		}else{
			st.insert(e[i].y);
		}
	}
	puts("Yes");
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)solve();
}

标签:巧克力,盒子,int,题解,Wrapping,Chocolate,ABC245E
From: https://www.cnblogs.com/yinhee/p/ABC245E.html

相关文章

  • java.sql.SQLSyntaxErrorException: Table 'test.user' doesn't exist报错问题解决
    以下内容仅供自己学习使用,侵权必删在使用mubatis-plus的时候报错了以下内容java.sql.SQLSyntaxErrorException:Table'test.user'doesn'texist解决方法:2.1在......
  • CF1804F Approximate Diameter 题解
    前言在学校机房被学长推荐了这道题,听完正解后惊为天人...简化版题面给定一张无向连通图,定义直径\(d=\max(dis(i,j))\quad(i,j\inN)\),其中\(dis(i,j)\)指的是\(......
  • 【题解】ABC293E Sol
    题目大意给定整数\(A,X,M\),求\(\sum\limits^{X-1}_{i=0}A^i\)对\(M\)取模的值。数据范围:\(1\leA,M\le10^9\),\(1\leX\le10^{12}\)。题目分析直接算显然......
  • h5中audio无法播放问题解决
    H5页面中添加audio标签,通过调用play()方法进行播放音频,电脑可以正常听到音效,微信中打开没有声音。<audioid="audio"ref="audio"class="sound"><sourcesrc="@/st......
  • 【微电平台】-高并发实战经验-奇葩问题解决之旅
    作者:京东科技孙亮微电平台微电平台是集电销、企业微信等于一体的综合智能SCRMSAAS化系统,涵盖多渠道管理、全客户生命周期管理、私域营销运营等主要功能,目前已经有60+京东......
  • Centos7系统在开启进入系统报错:Give root password for maintenance(or type Control-D
    报错信息:在进入系统时,不能正常进入系统,出现了Giverootpasswordformaintenance(ortypeControl-Dtocontinue):的报错。 报错原因:1、在之前写入的/etc/fstab文件有......
  • 【题解】UOJ#37. [清华集训2014]主旋律
    我自己写的代码自己都看不懂。所以芝士一种船新做法,爱来自学弟,lc学长好工作。题意校内OJ的题面过于简洁,人话:给定一个有向的强连通图,问任意删边使得新图仍强连通的方......
  • 江南信息学2023第四周练习20230317 题解
    首先,通报批评上周抄袭题解的同学有:黄耿益,黄远鸿,博客提供题解不是让大家直接复制粘贴抄袭的,而是在大家不会做时提供思路和解决方案,可以抄写,但不允许直接复制粘贴抄袭,请养成......
  • conda 安装 rpy2 版本不匹配问题解决方法
    问题描述:Anaconda3(python3.8)安装rpy2(R4.0.4)时尝试使用condainstallrpy2安装,但是报错如下:UnsatisfiableError:Thefollowingspecificationswerefoundtobein......
  • Codeforces Round 851 (Div. 2) (CF1788) 题解
    CF1788AOneandTwo对于一个序列,题目要求蓝色部分的乘积等于绿色部分的乘积,因为序列中只有\(1\)和\(2\),所以我们只要蓝色部分和绿色部分的\(2\)的数量相等即可,使用......