首页 > 其他分享 >题解:AT_abc376_c [ABC376C] Prepare Another Box

题解:AT_abc376_c [ABC376C] Prepare Another Box

时间:2024-10-20 14:42:38浏览次数:8  
标签:Box 匹配 Prepare 题解 元素 数组 abc376

这道题要求把 \(a\) 数组和 \(b\) 数组一一匹配,且要求无法匹配的数量最多为一,并且这个无法匹配的元素最小。

可以注意到我们把两个数组排序以后一一对应以后如果出现一个无法匹配的元素,那么这一定就是答案。

但是如果我们从小到大枚举,会发现最后剩下的元素不一定最小,所以我们选择从大到小遍历。

具体的,如果我们遇到一个不能满足的元素,那么我们就让 \(a\) 数组的匹配位置前移继续匹配,并标记此元素为答案。如果后面再遇到一个无法匹配的元素,那么一定无解。

提交记录

标签:Box,匹配,Prepare,题解,元素,数组,abc376
From: https://www.cnblogs.com/Lydic/p/18487291

相关文章

  • abc376C Prepare Another Box
    有N个玩具,大小分别为A[i];另外有N-1个盒子,大小分别为B[i]。现要再买一个盒子,把所有玩具装到盒子里,要求每个玩具都装一个盒子,并且玩具大小不超过盒子大小。问买的盒子至少为多大?如果无法满足,输出-1。2<=N<=2E5,1<=A[i],B[i]<=1E9分析:将玩具按从大到小排序再依次处理,每次用不小于......
  • JDBC:Statement和PreparedStatement的区别分析
    StatementStatement用于执行静态的SQL查询,通常在SQL语句不会频繁变化的情况下使用。特点不支持参数化查询:SQL语句直接嵌入在代码中,在语句中添加参数较为麻烦。存在SQL注入风险:由于直接拼接字符串,容易受到SQL注入攻击。性能较低:每次执行SQL语句时,数据库都需要......
  • 【题解】「COCI 2018」Teoretičar
    LinkofThisProblem根据Vizing定理,最小的答案就是二分图的最大度数。同时可以在\(O(nm)\)的时间复杂度内构造出一组解。显然对于这道题我们需要更高效的做法。注意到\(2\)的整数次幂,考虑分治。既然答案跟最大度数有关,如果我们每次能把边集分为两个集合,认为她们的颜色......
  • ICPC 2021–2022,NERC – 北欧欧亚总决赛题解翻译
    原文链接ICPC2021–2022,NERC–北欧欧亚总决赛题解翻译圣彼得堡,阿拉木图,巴尔瑙尔,明斯克,埃里温,2022年4月13日问题A.可接受的地图(AdmissibleMap)问题作者和开发者:IlyaZban我们称形如“RLRL...RL”的任何字符串为平凡字符串。引理任何非平凡字符串最多只能有一个构成......
  • [ABC376E] Max × Sum 题解
    [ABC376E]Max×Sum题解原题链接洛谷链接一道简单的推性质题,首先明确一个性质,子集是非连续的,所以在计算时并不用连续区间求。拿过题来,首先想的是枚举\(B\)的最小子集,但其复杂度为\(O(C_N^K)\)复杂度过高,不足以通过本题。于是转变思路,枚举\(A\)之中的最大值。若\(a_i......
  • Ubuntu 24.04使用virtualBox启动虚拟机提示Kernel driver not installed的解决办法
    1.Ubuntu安装virtualBoxvirtualBox官方下载对应ubuntu24.04系统的deb安装包进入到下载文件所在目录使用如下apt命令安装下载好的deb安装包sudoaptinstall-f./virtualBox*2.启动虚拟机提示“Kerneldrivernotinstalled”由于我装的是双系统,ubuntu挂载了windows下使......
  • 整数去重-题解
    整数去重-题解题目描述给定含有n个整数的序列,要求对这个序列进行去重操作。所谓去重,是指对这个序列中每个重复出现的数,只保留该数第一次出现的位置,删除其余位置。输入格式输入包含两行:第一行包含一个正整数n(1<=n<=20000),表示第二行序列中数字的个数;第二行包含n个整数,整数......
  • P4050 麻将 题解
    不愧是ZJOI。题意:有\(n\)种麻将牌,每种四张。定义"胡牌"为小鸡胡或普通七小对。给定初始\(13\)张牌,将剩下\(4n-13\)张牌随机排列,问期望摸多少张牌能胡(假设采用最优决策)。\(n\le100\)。先考虑怎么判定是否胡牌。\(cnt[i]\)表示前\(i\)种牌能凑出多少个对子,\(f[i][j]......
  • P10532 [XJTUPC2024] 筛法 题解
    ~~打表可知答案为$n^2$~~一种几何证明,方法来自于讲评。考虑把$n^2$个整点放到坐标系中,满足$(x,y)(x\len,y\len)$。现在从原点向每个满足$(x,y)(x\perpy)$的点引出一条射线,显然每个点都会唯一的被一条射线覆盖到,因为$(\dfrac{x}{\gcd(x,y)},\dfrac{y}{\g......
  • P3571 [POI2014] SUP-Supercomputer 题解
    P3571「POI2014」SUP-Supercomputer题解一道“较”水的黑题(可一开始苦思冥想还是不会)。本蒟蒻的第一篇黑题题解,求赞。题意简化给定一棵$n$个节点、根节点为$1$的有根树。$q$次询问中每次给定一个$k$,输出需要最少用几次操作次数删除完整棵树。每次操作可以选择删......