牛客小白月赛136D题（二分查找+数论）

题目链接D-Flower_Rainbow_and_Grid_牛客小白月赛136题目大意给定一个n*m的网格对于第i行第j列的方格的值是i*i-j*j,求出网格中前k大的数字之和(对于每个测试文件nm之和不超过5e4)题目思路网格中第 i 行第 j 列的值为i^2 - j^2观察可知每行从左到右递减j 越大值越小问题转化为求所有 n*m 个值中前 k 大的和那么我们可以二分一个阈值 x统计所有 x 的数的个数和总和如果个数 k说明阈值可以更大否则阈值需要更小对于第 i 行需要统计满足 i^2 - j^2 x 的 j 的个数即 j^2 i^2 - x所以 j sqrt(i^2 - x)然后利用平方和公式 O(1) 计算该行的和sum((2*n1)*((1n)*n/2))/3计算最终答案1. 先统计所有 aim 的数即 aim 12. 还需要补足 (k - cnt) 个等于 aim的数代码如下#include bits/stdc.h using namespace std; #define int long long #define endl \n pairint,intcheck(int x,int n,int m){ int cnt 0, sum 0; for (int i 1; i n;i){ int max_j_sq i * i - x; if(max_j_sq1) { continue; } int max_j sqrt(max_j_sq); max_j min(max_j, m); if(max_j1){ cnt max_j; sum max_j * (1LL * i * i) - max_j * (max_j 1) * (2 * max_j 1) / 6; } } return {cnt, sum}; } void solve() { int n, m, k; cin n m k; int l -1e10, r 1e10; int aim l; //1 2 3 4 while(lr) { int mid (l r) / 2; pairint, int res check(mid, n, m); if(res.firstk){ aim mid; l mid 1; }else{ r mid - 1 ; } } pairint, int res check(aim 1, n, m); int ans res.second (k - res.first) * aim; cout ans endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { solve(); } return 0; }