编程之美一道简单的热身题,活生生的组合数学例子啊。
题意如下:
在 N 条水平线与 M 条竖直线构成的网格中,放 K 枚石子,每个石子都只能放在网格的交叉点上。问在最优的摆放方式下,最多能找到多少四边平行于坐标轴的长方形,它的四个角上都恰好放着一枚石子。
输入
输入文件包含多组测试数据。第一行,给出一个整数T(1 ≤ T ≤ 100)为数据组数。接下来依次给出每组测试数据。每组数据为三个用空格隔开的整数 N,M,K。(0 ≤ K ≤ N * M,0 < N, M ≤ 30000)。
输出
对于每组测试数据,输出一行"Case #X: Y",其中X表示测试数据编号,Y表示最多能找到的符合条件的长方形数量。所有数据按读入顺序从1开始编号。
样例输入
3
3 3 8
4 5 13
7 14 86
样例输出
Case #1: 5
Case #2: 18
Case #3: 1398
解题思路:
考虑对于一个布满点的网格(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-1)/2;
}
int main()
{
int T;
cin >> T;
for(int cnt = 1; cnt <= T; ++cnt)
{
int n, m, k;
cin >> n >> m >> k;
if(n > m) swap(n,m); //n为短边,m为长边(个人习惯~0~)
long long ans = 0;
for(int x = 2; 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 0;
}
原文链接: https://www.cnblogs.com/chenbjin/p/3649380.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/126407
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!