P9497 「RiOI-2」weight

记录146

#include<bits/stdc++.h> using namespace std; #define ll long long // 防止数据溢出，使用long long //n*n的矩阵，n是1e3 ，所以N是1e6 const int N=1e6+5; ll a[N],n,q,cnt; // a数组存储打平后的矩阵，cnt记录总数字个数 // 从大到小排序的比较函数 bool cmp(ll a,ll b) { return a>b; } //因为每一行都可以“任意重排”，这就意味着我们拥有极大的自由度。我们可以把矩阵中所有 ≥v的数字像发牌一样，尽可能均匀地分配到不同的列里去。 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); // 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; }

题目传送门https://www.luogu.com.cn/problem/P9497

前言

我是一名专注信奥赛（CSP-J/S、NOIP）的教练。

• 如果你觉得这篇题解对你有帮助，欢迎点击关注我的CSDN账号，我会持续更新高质量算法解析。
• 我深知算法思维的构建远比单纯通过题目更重要，本系列题解不局限于AC代码的堆砌，而是致力于拆解题目背后的逻辑链条与核心知识点
• 备赛路上若遇瓶颈，欢迎随时评论或私信，我将甄选典型疑难问题，通过视频讲解或撰写专项文章的形式，为你提供深度答疑。

代码分块详细解释

1. 头文件、常量与全局变量定义

#include<bits/stdc++.h> using namespace std; #define ll long long // 防止数据溢出，使用 long long // n*n的矩阵，n是1e3，所以总元素个数是1e6 const int N=1e6+5; ll a[N], n, q, cnt; // a数组存储打平后的矩阵，cnt记录总数字个数

• 详细分析：矩阵的最大规模是 10^3×10^3=10^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)。

核心逻辑总结表