长方形—C++

编程之美一道简单的热身题，活生生的组合数学例子啊。

题意如下：

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

输入

　　输入文件包含多组测试数据。第一行，给出一个整数T（1 ≤ T ≤ 100）为数据组数。接下来依次给出每组测试数据。每组数据为三个用空格隔开的整数 N，M，K。（0 ≤ K ≤ N * M，0 < N, M ≤ 30000）。

输出

　　对于每组测试数据，输出一行"Case #X: Y"，其中X表示测试数据编号，Y表示最多能找到的符合条件的长方形数量。所有数据按读入顺序从1开始编号。

样例输入

样例输出

Case #:

Case #:

Case #:

解题思路：

　　考虑对于一个布满点的网格(x行，Y列)，所有的矩形总数为组合数C(2,x)*C(2,y)。但k不一定刚好就能布满整个网格，所以我们先找到在网格中最大能形成的长方形矩阵的长y和宽x，剩余石子为r，则有k = x * y + r , 最大能形成的长方形矩阵最多有C(x,2)*C(y,2)个矩形，剩余石子 r 以一排或一列的形式，靠在大矩形短的一边（要注意是否到达边界），则多增加的矩形数为 C(2,r)*y （y为长边的点数）。枚举x与y，计算出C(x,2)*C(y,2)+ C(r,2)*y的最大值。

代码如下：

#include <iostream>

#include <cmath>

#include <algorithm>

using namespace std;

long long Func(long long n)

{

    return n*(n-)/;

}

int main()

{

    int T;

    cin >> T;

    for(int cnt = ; cnt <= T; ++cnt)

    {

        int n, m, k;

        cin >> n >> m >> k;

        if(n > m) swap(n,m);    　　　　//n为短边，m为长边（个人习惯~0~）

        long long ans = ;

        for(int x = ; x <= n; ++x)   //对x进行枚举（短边）

        {

            int y = k / x;     　　　　//可能的最大长边y

            int r = k % x;     　　　　//剩余的石子数r

            if( y > m || ( y == m && r) )   //超边界

                continue;

            ans = max(ans, Func(x)*Func(y) + y*Func(r));

        }

        cout << "Case #" << cnt << ": " << ans << endl;

    }

    return ;

}

巴特西

长方形—C++

最新文章

热门文章