频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
编程之美 正方形
2014-04-10 11:32:47         来源:编程之美 正方形  
收藏   我要投稿

时间限制: 1000ms 内存限制: 256MB

描述

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

输入

输入文件包含多组测试数据。

第一行,给出一个整数T,为数据组数。接下来依次给出每组测试数据。

每组数据为三个用空格隔开的整数 N,M,K。

输出

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

数据范围

1 ≤ T ≤ 100

0 ≤ K ≤ N * M

小数据:0 < N, M ≤ 30

大数据:0 < N, M ≤ 30000

样例输入

3

3 3 8

4 5 13

7 14 86

样例输出

Case #1: 5

Case #2: 18

Case #3: 1398



解题思路

最优的方案总是先将一部分石子先排成一个满的n行m列矩形,然后再加上不满一行的石子构成的零头。

具体做法分别枚举以行或列为基准,更新答案。

#include 
#include 
#include 
#include 
typedef long long ll;
using namespace std;

int main(){
	int T;
	scanf("%d", &T);
	for(int t = 0; t < T; t++){
		int n, m, k;
		scanf("%d %d %d", &n, &m, &k);
		ll ans = 0;
		for(int i = 1; i <= n; i++){
			int l = i;
			int r = k / i;
			if(r > m) continue;
			int rem = k % i;
			if(rem && r == m) continue;
			ans = max(ans, (ll)(l - 1) * l * (r - 1) * r / 4 + (ll)(rem - 1) * (rem) * r / 2);
		}
		swap(n,m);
		for(int i = 1; i <= n; i++){
			int l = i;
			int r = k / i;
			if(r > m) continue;
			int rem = k % i;
			if(rem && r == m) continue;
			ans = max(ans, (ll)(l - 1) * l * (r - 1) * r / 4 + (ll)(rem - 1) * (rem) * r / 2);
		}
		printf("Case #%d: %lld\n",t+1,ans);
	}
}




点击复制链接 与好友分享!回本站首页
相关TAG标签 之美 正方形
上一篇:面向对象——多态
下一篇:java中对象的比较---==与equals的使用注意事项
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站