P9497 「RiOI-2」weight

记录146#includebits/stdc.h using namespace std; #define ll long long // 防止数据溢出使用long long //n*n的矩阵n是1e3 所以N是1e6 const int N1e65; ll a[N],n,q,cnt; // a数组存储打平后的矩阵cnt记录总数字个数 // 从大到小排序的比较函数 bool cmp(ll a,ll b) { return ab; } //因为每一行都可以“任意重排”这就意味着我们拥有极大的自由度。我们可以把矩阵中所有 ≥v的数字像发牌一样尽可能均匀地分配到不同的列里去。 int main() { ios::sync_with_stdio(false); // 关闭同步加速IO cin.tie(0); cinnq; // 1. 读入矩阵并打平成一维数组 for(ll i1;in;i) { for(ll j1;jn;j) { cina[cnt]; } } // 2. 预处理从大到小排序 sort(a1,acnt1,cmp); // 3. 处理每次询问 while(q--) { ll x; cinx; ll ans0,l1,rcnt; // 手写二分查找寻找最后一个 x 的位置 while(lr) { ll mid(lr)/2; if(a[mid]x) { rmid-1; // 中间值小于x说明答案在左边 } else { lmid1; // 中间值x更新答案并向右寻找 ansmid; } } // 满足条件的数字个数不能超过矩阵的列数 n coutmin(ans,n)\n; } return 0; }题目传送门https://www.luogu.com.cn/problem/P9497前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。代码分块详细解释1. 头文件、常量与全局变量定义#includebits/stdc.h using namespace std; #define ll long long // 防止数据溢出使用 long long // n*n的矩阵n是1e3所以总元素个数是1e6 const int N1e65; ll a[N], n, q, cnt; // a数组存储打平后的矩阵cnt记录总数字个数详细分析矩阵的最大规模是 10^3×10^310^6 因此数组大小需要开到 10^6级别。由于矩阵中的数值和阈值 vv 最高可达 10^9 为了防止潜在的溢出风险代码统一使用了long long类型。cnt变量用于在读取矩阵时充当一维数组的索引计数器。2. 排序比较函数// 从大到小排序的比较函数 bool cmp(ll a, ll b) { return a b; }详细分析标准库的sort默认是升序排列。为了方便后续的二分查找我们希望 ≥v≥v 的数字集中在数组的前端这里自定义了一个降序排列的比较函数。3. 主函数输入处理与预处理int main() { ios::sync_with_stdio(false); // 关闭同步加速IO cin.tie(0); cin n q; // 1. 读入矩阵并打平成一维数组 for(ll i 1; i n; i) { for(ll j 1; j n; j) { cin a[cnt]; } } // 2. 预处理从大到小排序 sort(a 1, a cnt 1, cmp);详细分析这部分完成了核心的预处理。通过双重循环将二维矩阵的 n^2个元素全部读入一维数组a中。随后调用sort进行降序排序。这一步的时间复杂度是 O(n2log⁡n2) 由于只执行一次完全可以接受。4. 核心逻辑处理询问与手写二分// 3. 处理每次询问 while(q--) { ll x; cin x; ll ans 0, l 1, r cnt; // 手写二分查找寻找最后一个 x 的位置 while(l r) { ll mid (l r) / 2; if(a[mid] x) { r mid - 1; // 中间值小于x说明答案在左边 } else { l mid 1; // 中间值x更新答案并向右寻找 ans mid; } } // 满足条件的数字个数不能超过矩阵的列数 n cout min(ans, n) \n; } return 0; }详细分析这是代码的灵魂部分用于处理高达 5×1055×105 次的询问。手写二分对于当前的阈值 xx 我们需要找出数组中有多少个元素 ≥x≥x 。由于数组是降序的所有 ≥x≥x 的元素会连续出现在数组的前端。二分查找的else分支a[mid] x会不断向右推进l并用ans记录下当前满足条件的最右位置。循环结束后ans就是 ≥x≥x 的元素总个数。贪心取最小值ans代表了理论上能凑出的最大列数。但如果ans n比如矩阵里全是 ≥x≥x 的大数ans达到了 n2n2 受限于矩阵只有 nn 列我们最多只能让 nn 列达标。因此最终输出min(ans, n)。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点矩阵打平cin a[cnt]将二维矩阵转化为一维数组打破行列的物理限制便于全局统计和排序降序预处理sort(..., cmp)将数组按从大到小排列使得所有 ≥v≥v 的元素集中在数组前端为二分查找提供单调性基础