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

题解：AtCoder AT_awc0080_b Quality Inspection and Product Disposal

news 2026/6/13 12:47:51

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

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

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

【题目来源】

AtCoder：B - Quality Inspection and Product Disposal

【题目描述】

Takahashi is the quality control manager of a factory. The factory has a system where manufactured products are periodically inspected for quality, and products that do not meet the standards are disposed of.

The factory currently hasN NNproducts, each numbered from1 11toN NN. The quality score of producti iiisA i A_iAi.

Takahashi performsQ QQquality inspections in order. In thej jj-th inspection( 1 ≤ j ≤ Q ) (1 \leq j \leq Q)(1≤j≤Q), a threshold valueT j T_jTjis set, andamong the products that have not yet been disposed of at that point, all products whose quality score isstrictly less thanT j T_jTjare disposed of. Once a product is disposed of, it is no longer subject to subsequent inspections. Note that the threshold valueT j T_jTjis determined independently for each inspection, so it may be smaller than the previous threshold. In that case, if the relevant products have already been disposed of in previous inspections, no new products are disposed of.

Immediately after each inspection, the number of products newly disposed of in that inspection is recorded. For allQ QQquality inspections, determine the number of products newly disposed of in each inspection.

高桥是工厂的质量控制经理。工厂有一个系统，定期检查产品的质量，不符合标准的产品会被销毁。

工厂目前有N NN个产品，编号从1 11到N NN。产品i ii的质量得分为A i A_iAi。

高桥按顺序执行Q QQ次质量检查。在第j jj次检查中（1 ≤ j ≤ Q 1 \leq j \leq Q1≤j≤Q），设定一个阈值T j T_jTj，并且在此时尚未销毁的产品中，所有质量得分严格小于T j T_jTj的产品将被销毁。一旦产品被销毁，它将不再受后续检查的影响。注意，每次检查的阈值T j T_jTj是独立确定的，因此它可能小于之前的阈值。在这种情况下，如果相关产品在之前的检查中已经被销毁，则不会再有新产品被销毁。

每次检查后，立即记录该次检查中新销毁的产品数量。对于所有Q QQ次质量检查，确定每次检查中新销毁的产品数量。

【输入】

N NNQ QQ
A 1 A_1A1A 2 A_2A2… \ldots…A N A_NAN
T 1 T_1T1
T 2 T_2T2
⋮ \vdots⋮
T Q T_QTQ

The first line contains an integerN NNrepresenting the number of products and an integerQ QQrepresenting the number of quality inspections, separated by a space.
The second line contains integersA 1 , A 2 , … , A N A_1, A_2, \ldots, A_NA1,A2,…,ANrepresenting the quality scores of each product, separated by spaces.
In the followingQ QQlines, thej jj-th line( 1 ≤ j ≤ Q ) (1 \leq j \leq Q)(1≤j≤Q)contains an integerT j T_jTjrepresenting the threshold value for thej jj-th inspection.

【输出】

OutputQ QQlines. Thej jj-th line( 1 ≤ j ≤ Q ) (1 \leq j \leq Q)(1≤j≤Q)should contain the number of products newly disposed of in thej jj-th inspection.

【输入样例】

5 3 3 1 4 1 5 2 4 3

【输出样例】

2 1 0

【算法标签】

#整数二分

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=200005;intn,q,st;// n: 数组长度，q: 查询次数，st: 起始位置inta[N];// 存储数组intmain(){cin>>n>>q;// 输入数组长度和查询次数for(inti=1;i<=n;i++)// 输入数组元素cin>>a[i];sort(a+1,a+n+1);// 对数组进行升序排序st=1;// 初始化起始位置为1while(q--)// 处理每个查询{intt;// 查询值cin>>t;// 输入查询值intpos=upper_bound(a+1,a+n+1,t-1)-a;// 找到第一个大于t-1的位置if(pos<=st)// 如果位置小于等于起始位置cout<<0<<endl;// 输出0elsecout<<pos-st<<endl;// 输出区间长度st=max(st,pos);// 更新起始位置}return0;}