【Codeforces 449A】Jzzhu and Chocolate

题意

【题解】

设最后行分成了x行,列分成了y列。
那么答案就是floor(n/x)*floor(n/y)
然后x+y-2=k
//即平均分配x行、y列
我们可以枚举floor(n/x)的值
这个值其实就是n整除x
我们现在证明n/x的结果最多只可能有2*sqrt(n)个
证明:
当x小于$\sqrt{n}$时,n/x的值有$\sqrt{n}$个。
当x大于$\sqrt{n}$时,n/x的结果肯定小于$\sqrt{n}$,因此也只可能有$\sqrt{n}$个数字
所以综上,n/x的结果最多只可能有2*$\sqrt{n}$个数字
所以我们可以把1..$\sqrt{n}$和n/1,n/2...n/$\sqrt{n}$的值全都枚举一遍。
假设他们是n/x,然后求出最大的x(x越大,y就越小,m/y就越大),即n/这个数字。
然后算出来还剩下多少刀可以切在列上。
如果剩余的刀数小于0的话
不要忘记,我们是求出来最大的x,因此我们总是可以减少在行上切的刀数的(但最小的间距还是可以不变),然后让剩余的刀数变为0即可。
但是如果剩余刀数大于m-1了,那就说明行上能切的次数太少了,不能满足切成x行,即n/x取该值不合法

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

ll n,m,k;

vector<ll> v;

int main()

{

    cin >> n >> m >> k;

    for (int i = 1;i*i <= n;i++){

        v.push_back(n/i);

        v.push_back(i);

    }

    ll ans = -1;

    int len = v.size();

    for (int ii = 0;ii < len;ii++){

        //n/x

        ll ndx = v[ii];

        ll x = n/ndx;

        ll rest = k-(x-1);

        if (rest<0) rest = 0; //如果行砍的边太多了,可以少砍一点的,只要x个单位长度的连续边就好

        if (rest>m-1) continue; //如果行砍得太少了则没有办法,因为没办法再多砍了

        ll y = rest + 1;

        if (ndx*(m/y)>ans){

            ans = ndx*(m/y);

        }

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

【Codeforces 449A】Jzzhu and Chocolate

最新文章

热门文章