Codeforces Round #256 (Div. 2) Multiplication Table-白红宇

Codeforces Round #256 (Div. 2) Multiplication Table

阅读量：5331 次

发布时间：2019-06-15

本文共 1380 字，大约阅读时间需要 4 分钟。

C题，

#include
      
       #include
       
        #include
        
         #define maxn 5005using namespace std;int num[maxn];int rmq(int l,int r){    int ans=1<<30,tmp=l;    for(int i=l;i<=r;i++)    {        if(ans>num[i])        {            ans=num[i];            tmp=i;        }    }    return tmp;}int get(int l,int r,int h){    if(l>r)        return 0;    if(l==r)    {        if(num[l]==h)            return 0;        else return 1;    }    int tmp=rmq(l,r);    int ans=0;    ans=min(r-l+1,get(l,tmp-1,num[tmp])+get(tmp+1,r,num[tmp])+num[tmp]-h);    return ans;}int main(){    int n;    scanf("%d",&n);    for(int i=0;i

View Code

刚刚开始想到一种很暴力但还行的方法，不过在和TK讨论的过程中引出了一个更好的算法

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;long long n,m,k;long long check(long long x){    long long ans=0;    for(int i=1;i<=n;i++)    {        ans+=min(x/i,m);        if(min(x/i,m)*i==x)            ans--;    }    return ans;}int main(){    scanf("%I64d%I64d%I64d",&n,&m,&k);    long long l=1,r=n*m+3;    long long ans=0;    while(l
          
           >1;        long long a=check(mid);        long long b=check(mid+1);        if(a
           
            =k) { ans=mid; break; } else if(b
            
             =k)r=mid; } cout<
             
              <