题解：AtCoder AT_awc0031_d Library Inventory Check

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

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

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

【题目来源】

AtCoder：D - Library Inventory Check

【题目描述】

Takahashi is working as a librarian and is in charge of a book inspection spanningN NNdays.
高桥是一名图书馆员，负责一项为期N NN天的书籍检查工作。

This library hasM MMbooks. To ensure that no deterioration or damage to books is overlooked, a standard has been established that each bookj jj( 1 ≤ j ≤ M ) (1 \leq j \leq M)(1≤j≤M)must be inspected on at leastR j R_jRj​days out of theN NNdays.
这个图书馆有M MM本书。为了确保不遗漏书籍的劣化或损坏，制定了一个标准：每本书j jj（1 ≤ j ≤ M 1 \leq j \leq M1≤j≤M）在N NN天中至少需要被检查R j R_jRj​天。

On the other hand, the maximum number of books that can be inspected on dayi ii( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N)isL i L_iLi​. Also, the same book cannot be inspected multiple times on the same day, but the same book can be inspected again on a different day.
另一方面，每天i ii（1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N）最多可以检查L i L_iLi​本书。此外，同一本书在同一天不能被检查多次，但同一本书可以在不同日期再次检查。

Takahashi is free to decide which books to inspect on which days. Determine whether it is possible to create an inspection plan that satisfies the inspection requirements for all books.
高桥可以自由决定在哪天检查哪些书。判断是否有可能制定一个满足所有书籍检查要求的检查计划。

Specifically, determine whether there exists an inspection plan that satisfies all of the following conditions:
具体来说，判断是否存在一个满足以下所有条件的检查计划：

• The number of books inspected on each dayi iiis at mostL i L_iLi​.
  每天i ii检查的书籍数量不超过L i L_iLi​。
• The same book is not inspected more than once on the same day.
  同一本书在同一天不被检查超过一次。
• The total number of days each bookj jjis inspected is at leastR j R_jRj​.
  每本书j jj被检查的总天数至少为R j R_jRj​。

【输入】

N NNM MM
L 1 L_1L1​L 2 L_2L2​… \ldots…L N L_NLN​
R 1 R_1R1​R 2 R_2R2​… \ldots…R M R_MRM​

• The first line containsN NN, the number of days in the inspection period, andM MM, the number of books, separated by a space.
• The second line containsL 1 , L 2 , … , L N L_1, L_2, \ldots, L_NL1​,L2​,…,LN​, the maximum number of books that can be inspected on each day, separated by spaces.
• The third line containsR 1 , R 2 , … , R M R_1, R_2, \ldots, R_MR1​,R2​,…,RM​, the required number of inspection days for each book, separated by spaces.

【输出】

If an inspection plan that satisfies the inspection requirements for all books exists, printYes; otherwise, printNoon a single line.

【输入样例】

3 4 2 3 2 1 2 1 2

【输出样例】

Yes

【解题思路】

【算法标签】

#贪心#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=200005;intn,m;intl[N],r[N];// l: 学生数组, r: 老师数组signedmain(){cin>>n>>m;for(inti=1;i<=n;i++){cin>>l[i];}for(inti=1;i<=m;i++){cin>>r[i];}sort(l+1,l+n+1);// 对学生能力排序sort(r+1,r+m+1,greater<int>());// 对老师要求降序排序intsuml=0,sumr=0;// suml: 学生总能力, sumr: 老师总要求for(inti=1;i<=m;i++)// 遍历老师{sumr+=r[i];// 累加老师要求// 查找第一个能力 >= i 的学生位置intpos=lower_bound(l+1,l+n+1,i)-l;// 能力 >= i 的学生数量suml+=(n-(pos-1));// 如果当前学生的总能力小于老师总要求if(suml<sumr){cout<<"No"<<endl;return0;}}cout<<"Yes"<<endl;return0;}

【运行结果】

3 4 2 3 2 1 2 1 2 Yes