ABC382&ABC383题解
Kaiten Sushi题目描述
有 \(N\) 个人，编号从 \(1\) 到 \(N\)，他们正在访问一家传送带寿司餐厅。第 \(i\) 个人的美食级别是 \(A_i\)。
现在，将会有 \(M\) 份寿司放置在传送带上。第 \(j\) 份寿司的美味度为 \(B_j\)。每份寿司将按照顺序经过编号为 \(1\)，\(2\)，\(\dots\)，\(N\) 的人。每个人在看到美味度不低于他们美食级别的寿司经过时，会拿走并吃掉那份寿司；否则，他们什么也不做。一旦第 \(i\) 个人拿走并吃掉了寿司，那份寿司就不会再经过编号大于 \(i\) 的人。
对于每份 \(M\) 份寿司中的一份，请确定是谁吃掉了那份寿司，或者是否没有人吃掉它。
约束条件
\(1\le N\)，\(M\le2\times10^5\)
\(1\le A_i\)，\(B_i\le2\times10^5\)
所有输入值均为整数。
制約
[*]$ 1\leq\ N,M\ \leq\ 2\times\ 10^5 $
[*]$ 1\leq\ A_i,B_i\ \leq\ 2\times\ 10^5 $
[*]入力は全て整数
解题思路
以吃寿司的人为单位构造结构体，存储位置和美食级别。吃寿司的时候跟位置有关系，如果在后面的人的美食级别比前面的人还高的话，那肯定一口都吃不到，所以没必要存储。
所以存储的优先级第一为位置，第二为美食级别。存的一定是位置递增和美食级别递减的序列。
可以发现，对于美味度为\(d\)的寿司而言，如果能够被吃，一定是在这个序列当中美食级别第一个小于\(d\)的位置被吃的。因此可以考虑使用二分来解决该问题，总时间复杂度为\(O(nlogn)\)
将存储序列逆序排列，那么要找到的就是序列里小于等于\(d\)且最接近\(d\)的元素。因此注意二分的写法应当是
mid = (l + r + 1) / 2;
if(check()) l = mid;
else r = mid - 1;参考代码为：
//abc382c#include#include#includeusing namespace std;const int N = 200005;int a, b;struct pp{ int val, idx;}p;bool cmp(pp a, pp b){ return a.val < b.val;}int main(){ int n, m; cin >> n >> m; int minn = 0x3f3f3f, idx = 0; for(int i = 1; i > a; if(a < minn){ minn = a; p[++idx].val = a; p.idx = i; } } sort(p, p+idx+1, cmp); int min_val = p.val; for(int i = 1; i > b; if(b < min_val){ cout
页:
[1]