当前位置：首页 > news >正文

题解：AtCoder AT_awc0002_d Keys and Treasure Boxes

news 2026/4/21 2:45:38

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：D - 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 ii（1 ≤ 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 jj（1 ≤ 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 MM
C 1 C_1C1C 2 C_2C2… \ldots…C N C_NCN
R 1 R_1R1R 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,…,CNrepresenting 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,…,RMrepresenting 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

【输出样例】

【解题思路】

【算法标签】

#双指针#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=200005;intn,m;// n: 商品数量，m: 优惠券数量intc[N],r[N];// c: 商品价格数组，r: 优惠券金额数组intmain(){cin>>n>>m;// 读入商品数量和优惠券数量for(inti=1;i<=n;i++){cin>>c[i];// 读入第i个商品的价格}for(inti=1;i<=m;i++){cin>>r[i];// 读入第i张优惠券的金额}// 对商品价格进行升序排序，从下标1到nsort(c+1,c+n+1);// 对优惠券金额进行升序排序，从下标1到msort(r+1,r+m+1);intcnt=0;// 计数器，记录有多少商品可以使用优惠券// 双指针贪心匹配inti=1,j=1;// i: 商品指针，指向当前要处理的商品；j: 优惠券指针，指向当前要使用的优惠券// 当还有商品未处理且还有优惠券可用时，继续匹配while(i<=n&&j<=m){// 跳过所有金额小于当前商品价格的优惠券// 因为优惠券金额必须大于等于商品价格才能使用while(j<=m&&r[j]<c[i]){j++;// 当前优惠券金额太小，尝试下一张优惠券}// 如果还有可用的优惠券（即找到了金额>=商品价格的优惠券）if(j<=m){i++;// 处理下一个商品j++;// 使用当前优惠券，并指向下一张优惠券cnt++;// 成功匹配一个商品，计数器加1}else// 如果没有可用的优惠券了（所有优惠券金额都小于当前商品价格）{i++;// 当前商品无法使用任何优惠券，处理下一个商品}}cout<<cnt<<endl;// 输出能使用优惠券的商品数量return0;}