P9497 「RiOI-2」weight——二分

二分

P9497

思路

有 q 组询问，每次给定一个 v，请将矩阵每一行任意重排（可以不重排），最大化最大值不小于 v（也就是说，至少有一个不小于 v 的数）的列数。请输出这个列数。

也就是说：

找到所有数的最大的n个数依次分布在这n列中（因为答案只和每列的最大值相关，所以可以压缩为一维数组）

因此——用一维数组a保存二维数组中最大的n个数，然后用二分查找，找到a数组中第一个大于等于v的坐标i，输出n-i

代码

#include <bits/stdc++.h>
using namespace std;int n, a[1010], q, v;
int b[1000010];
long long int cnt;bool check(int x)
{return x >= v;
}int SL(int x)
{int l = 0, r = n - 1;while (l < r){int mid = l + r >> 1;if (check(a[mid])) r = mid;else l = mid + 1;}return l;
}int main()
{cin >> n >> q;for (int j = 0; j < n; j ++ )for (int i = 0; i < n; i ++ ){int x;cin >> x;b[cnt++] = x;}sort(b, b + cnt);for (int i = 0; i < n; i ++ ){a[i] = b[cnt - n + i];}while (q -- ){cin >> v;int ans = n - SL(v);// 满足a[i]>=v的最小值 n = 10, i = 3, 0123456789 , ans = 10 - 3if (v > a[n - 1]) ans = 0;cout << ans << endl;// cout << SL(v) << endl;// 可以用STL二分// cin >> v;// auto it = lower_bound(a, a + n, v);// // ≥v的元素数量// int num = a + n - it;// cout << num << endl;        }// // // cout << "1" << endl;return 0;
}