题意
好像是《挑战程序设计竞赛》上面的原题。题意是给你一个矩阵上每一项的位置与值对应的公式，让你求第k小的项。
思路
我们仔细看公式会发现对于每一个固定的j，公式结果随i单调递增，这样我们可以二分答案，对于mid值，我们在每一列再二分一次，求出比这个数小的数的个数，然后每一列的个数相加，就是这个数的排名。然后这个排名可以作为二分中判定的基准。这里还有一种替代思路，就是对于每一列不二分，而是解一个二次方程直接求出每一列的分排名。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; inline long long f(long long i,long long j){ return i*i+j*j+100000*i+i*j-100000*j; } bool ok(long long MID,long long n,long long m){ long long cnt = 0; for (int j = 1; j <= n; j++) { long long high = n+1,low = 1,mid = (n+2)/2; while (high > low) { if (f(mid,j) >= MID) { high = mid; }else{ low = mid+1; } mid = (high+low)>>1; } cnt += mid-1; } return cnt >= m; } int main(){ int caseCnt = 0; scanf(" %d",&caseCnt); for (int xi = 1;xi <= caseCnt; xi++) { long long n = 0,m = 0; scanf(" %lld %lld",&n,&m); long long high = 1e12,low = -1e12,mid = 0; while (high > low) { if (ok(mid,n,m)) { high = mid; }else{ low = mid+1; } mid = (high+low)>>1; } printf("%lld\n",mid-1); } return 0; } |
