jzoj 3452_长方形_模拟

发布于 2019-05-24  24 次阅读


思路

鸡腿想到了一个很高(sha)明(bi)的问题,在 N 条水平线与 M 条竖直线构成的网格中,放 K 枚石子,每个石子都只能放在网格的交叉点上。问在最优的摆放方式下,最多能找到多少四边平行于坐标轴的长方形,它的四个角上都恰好放着一枚石子。


思路

枚举一个矩形的边的长度,暴力判断即可
然后将n,m对调再跑一遍,输出最优解


#include 
#include 
#include 
using namespace std;
#define fill(x, y) memset(x, y, sizeof(x))
#define maxn 1001
#define LL long long
int main()
{
    freopen("rectangle.in","r",stdin);
    freopen("rectangle.out", "w", stdout);
    LL n, m, k, maxx = 0;
    scanf("%lld%lld%lld", &n, &m, &k);
    for (int i = 2; i <= n; i++)
        if (i * m >= k)
        {
            LL ans1 = i * (i - 1) / 2;
            int x = k / i;
            ans1 *= x * (x - 1) / 2;
            int y = k % i;
            ans1 += x * (y * (y - 1)) / 2;
            maxx = maxx > ans1 ? maxx : ans1;
        }
    n ^= m; m ^= n; n ^= m;
    for (int i = 2; i <= n; i++)
        if (i * m >= k)
        {
            LL ans1 = i * (i - 1) / 2;
            int x = k / i;
            ans1 *= x * (x - 1) / 2;
            int y = k % i;
            ans1 += x * (y * (y - 1)) / 2;
            maxx = maxx > ans1 ? maxx : ans1;
        }
    if (n == 1 || m == 1) maxx = 0;
    printf("%lld\n", maxx);
}
]]>