首页 > 代码库 > CF_448D 二分

CF_448D 二分

2024-07-12 17:39:34   218人阅读

给定n m k

n和m为一个矩阵的行和列，都从1开始，矩阵的每个元素的值即为 i*j（行*列），求里面第k个数

还想找什么规律，发现虽然矩阵里面很有规律，但是n 和m在不断变化 根本不好找

其实元素从 1 到 n*m，直接二分，每次二分完后，枚举所有行，通过min(mid/i,m)可以马上得到该行小于等于mid的个数，。。。接下来就不用说了吧

不过有点坑的就是某个数值在矩阵里面可能出现多次，比如12 可以由 1*12 2*6 3*4.。。来得到，然后这些重复的数字占用了多个大小位置，为了摆脱这个，一个比较好的方案就是  先 得到比 mid小的个数，如果正好等于k，就可以输出了，如果大于k，就把R边界缩小，如果小于k就要注意了，则判断<mid+1的数的个数a，如果a>=k,则第k个值肯定是mid了。。这里就可以查重，如果仍然小于，则继续缩小L边界

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define LL __int64using namespace std;int main(){    LL n,m,k;    while (scanf("%I64d%I64d%I64d",&n,&m,&k)!=EOF)    {        LL L=1,R=n*m+1;        LL mid;        LL ans=0;        while (L<R)        {            mid=(L+R)>>1;            LL sum=0;            LL maxn=0;            for (LL i=1;i<=n;i++){                LL tmp=min((mid-1)/i,m);                sum+=tmp;                if (tmp==0) break;                if (maxn<i*tmp){                    maxn=i*tmp;                }            }            if (sum==k){                ans=maxn;                break;            }            if (sum>k){                R=mid;                continue;            }            LL sum2=0;            if (sum<k){                for (LL i=1;i<=n;i++){                    LL tmp=min(mid/i,m);                    sum2+=tmp;                    if (tmp==0) break;                }                if (sum2>=k){                    ans=mid;                    break;                }                L=mid+1;            }        }        printf("%I64d\n",ans);    }    return 0;}

　　


联系
我们