codeforces#256DIV2 D题Multiplication Table

全栈程序员站长

发布于 2022-07-07 17:42:14

1830

发布于 2022-07-07 17:42:14

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是全栈君。

当时是依照找规律做的，规律倒是找出来了，可是非常麻烦非常麻烦。

。

看到前几名的红名爷们3分钟就过了，于是果断放弃了。

。赛后才知道是用二分的方法做，知道了二分之后。剩下的就非常easy了。。关键在于能不能想到用二分。。

代码例如以下：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include<algorithm>

using namespace std;

int main()
{
    __int64 low, high, mid, x, ans, s1, s2, n, m, k, i;
    scanf("%I64d%I64d%I64d",&n,&m,&k);
    high=n*m;
    low=1;
    while(low<=high)
    {
        mid=(low+high)/2;
        s1=s2=0;
        for(i=1;i<=n;i++)
        {
            x=mid/i;
            if(x>m)
            {
                s1+=m;
            }
            else
            {
                if(mid%i==0)
                {
                    s2++;
                    s1+=x-1;
                }
                else
                {
                    s1+=x;
                }
            }
        }
        if(k>=s1+1&&k<=s1+s2)
        {
            ans=mid;
            break;
        }
        else if(k>s1+s2)
        {
            low=mid+1;
        }
        else
        {
            high=mid-1;
        }
    }
    printf("%I64d\n",ans);
    return 0;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/116494.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年1月2，如有侵权请联系 cloudcommunity@tencent.com 删除

java