D - Library Inventory Check
【题目来源】
AtCoder：D - Library Inventory Check
【题目描述】
Takahashi is working as a librarian and is in charge of a book inspection spanning \(N\) days.
高桥是一名图书馆员，负责一项为期 \(N\) 天的书籍检查工作。
This library has \(M\) books. To ensure that no deterioration or damage to books is overlooked, a standard has been established that each book \(j\) \((1 \leq j \leq M)\) must be inspected on at least \(R_j\) days out of the \(N\) days.
这个图书馆有 \(M\) 本书。为了确保不遗漏书籍的劣化或损坏，制定了一个标准：每本书 \(j\)（\(1 \leq j \leq M\)）在 \(N\) 天中至少需要被检查 \(R_j\) 天。
On the other hand, the maximum number of books that can be inspected on day \(i\) \((1 \leq i \leq N)\) is \(L_i\). 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\)（\(1 \leq i \leq N\)）最多可以检查 \(L_i\) 本书。此外，同一本书在同一天不能被检查多次，但同一本书可以在不同日期再次检查。
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 day \(i\) is at most \(L_i\).
每天 \(i\) 检查的书籍数量不超过 \(L_i\)。 - The same book is not inspected more than once on the same day.
同一本书在同一天不被检查超过一次。 - The total number of days each book \(j\) is inspected is at least \(R_j\).
每本书 \(j\) 被检查的总天数至少为 \(R_j\)。
【输入】
\(N\) \(M\)
\(L_1\) \(L_2\) \(\ldots\) \(L_N\)
\(R_1\) \(R_2\) \(\ldots\) \(R_M\)
- The first line contains \(N\), the number of days in the inspection period, and \(M\), the number of books, separated by a space.
- The second line contains \(L_1, L_2, \ldots, L_N\), the maximum number of books that can be inspected on each day, separated by spaces.
- The third line contains \(R_1, R_2, \ldots, R_M\), 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, print Yes; otherwise, print No on a single line.
【输入样例】
3 4
2 3 2
1 2 1 2
【输出样例】
Yes
【解题思路】
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200005;int n, m;
int l[N], r[N]; // l: 学生数组, r: 老师数组signed main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> l[i];}for (int i = 1; i <= m; i++){cin >> r[i];}sort(l + 1, l + n + 1); // 对学生能力排序sort(r + 1, r + m + 1, greater<int>()); // 对老师要求降序排序int suml = 0, sumr = 0; // suml: 学生总能力, sumr: 老师总要求for (int i = 1; i <= m; i++) // 遍历老师{sumr += r[i]; // 累加老师要求// 查找第一个能力 >= i 的学生位置int pos = lower_bound(l + 1, l + n + 1, i) - l;// 能力 >= i 的学生数量suml += (n - (pos - 1));// 如果当前学生的总能力小于老师总要求if (suml < sumr){cout << "No" << endl;return 0;}}cout << "Yes" << endl;return 0;
}
【运行结果】
3 4
2 3 2
1 2 1 2
Yes