题解：AtCoder AT_awc0002_d Keys and Treasure Boxes

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderD - Keys and Treasure Boxes (atcoder.jp)【题目描述】After a long adventure, Takahashi has reached ruins containingN NNtreasure chests.经过漫长的冒险高桥抵达了藏有N NN个宝箱的遗迹。Each treasure chesti ii(1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N) is secured with a lock of strengthC i C_iCi​. A larger strength value means a sturdier lock. All treasure chests have mutually distinct lock strengths.每个宝箱i ii1 ≤ i ≤ N 1 ≤ i ≤ N1≤i≤N都配有一把强度为C i C_iCi​的锁。强度值越大意味着锁越坚固。所有宝箱的锁强度互不相同。Takahashi hasM MMkeys. Each keyj jj(1 ≤ j ≤ M 1 \leq j \leq M1≤j≤M) has an unlocking powerR j R_jRj​. Keyj jjcan open treasure chesti iionly if the key’s unlocking power is at least as large as the lock’s strength, that is, whenC i ≤ R j C_i \leq R_jCi​≤Rj​. Note that different keys may have the same unlocking power.高桥拥有M MM把钥匙。每把钥匙j jj1 ≤ j ≤ M 1 ≤ j ≤ M1≤j≤M具有开启能力R j R_jRj​。钥匙j jj仅当开启能力至少与锁的强度一样大时才能打开宝箱i ii即当C i ≤ R j C_i ≤ R_jCi​≤Rj​时。注意不同的钥匙可能具有相同的开启能力。Takahashi selects some treasure chests he wants to open (possibly0 00), and assigns exactly one key to each selected treasure chest to open it. However, the same key cannot be assigned to two or more treasure chests. Additionally, the key assigned to each treasure chest must be able to open it (C i ≤ R j C_i \leq R_jCi​≤Rj​). It is fine to leave some keys unused or some treasure chests unopened.高桥选择一些他想要打开的宝箱可能为0 00个并为每个被选中的宝箱分配恰好一把钥匙来打开它。然而同一把钥匙不能被分配给两个或更多宝箱。此外分配给每个宝箱的钥匙必须能够打开它C i ≤ R j C_i ≤ R_jCi​≤Rj​。可以留一些钥匙不使用也可以留一些宝箱不打开。Find the maximum number of treasure chests Takahashi can open.求高桥能够打开的最大宝箱数量。【输入】N NNM MMC 1 C_1C1​C 2 C_2C2​… \ldots…C N C_NCN​R 1 R_1R1​R 2 R_2R2​… \ldots…R M R_MRM​The first line contains an integerN NNrepresenting the number of treasure chests and an integerM MMrepresenting the number of keys, separated by a space.The second line contains integersC 1 , C 2 , … , C N C_1, C_2, \ldots, C_NC1​,C2​,…,CN​representing the lock strengths of the treasure chests, separated by spaces.The third line contains integersR 1 , R 2 , … , R M R_1, R_2, \ldots, R_MR1​,R2​,…,RM​representing the unlocking powers of the keys, separated by spaces.【输出】Print the maximum number of treasure chests Takahashi can open, on a single line.【输入样例】3 3 10 20 30 15 25 35【输出样例】3【解题思路】【算法标签】#双指针#【代码详解】#includebits/stdc.husingnamespacestd;constintN200005;intn,m;// n: 商品数量m: 优惠券数量intc[N],r[N];// c: 商品价格数组r: 优惠券金额数组intmain(){cinnm;// 读入商品数量和优惠券数量for(inti1;in;i){cinc[i];// 读入第i个商品的价格}for(inti1;im;i){cinr[i];// 读入第i张优惠券的金额}// 对商品价格进行升序排序从下标1到nsort(c1,cn1);// 对优惠券金额进行升序排序从下标1到msort(r1,rm1);intcnt0;// 计数器记录有多少商品可以使用优惠券// 双指针贪心匹配inti1,j1;// i: 商品指针指向当前要处理的商品j: 优惠券指针指向当前要使用的优惠券// 当还有商品未处理且还有优惠券可用时继续匹配while(injm){// 跳过所有金额小于当前商品价格的优惠券// 因为优惠券金额必须大于等于商品价格才能使用while(jmr[j]c[i]){j;// 当前优惠券金额太小尝试下一张优惠券}// 如果还有可用的优惠券即找到了金额商品价格的优惠券if(jm){i;// 处理下一个商品j;// 使用当前优惠券并指向下一张优惠券cnt;// 成功匹配一个商品计数器加1}else// 如果没有可用的优惠券了所有优惠券金额都小于当前商品价格{i;// 当前商品无法使用任何优惠券处理下一个商品}}coutcntendl;// 输出能使用优惠券的商品数量return0;}【运行结果】3 3 10 20 30 15 25 35 3