在 N 条水平线与 M 条竖直线构成的网格中，放 K 枚石子，每个石子都只能放在网格的交叉点上。问在最优的摆放方式下，最多能找到多少四边平行于坐标轴的长方形，它的四个角上都恰好放着一枚石子。
输入文件包含多组测试数据。
第一行，给出一个整数T，为数据组数。接下来依次给出每组测试数据。
每组数据为三个用空格隔开的整数 N，M，K。
1 ≤ T ≤ 100
0 ≤ K ≤ N * M
小数据：0 < N, M ≤ 30
大数据：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
#include "stdafx.h"
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int i,T,N[100],M[100],K[100],sum[100];
for(i=0;i<100;i++)
{
N[i]=0;
M[i]=0;
K[i]=0;
sum[i]=0;
}
cin>>T;
if((T<1||T>100))
return 0;
for(i=0; i<T;i++)
{
cin>>N[i]>>M[i]>>K[i];
if((N[i]<=0||N[i]>30000)||(M[i]<=0||M[i]>30000))
return 0;
}
for(i=0;i<T;i++)
{
if(N[i]>M[i])
{
int temp = N[i];
M[i] = N[i];
N[i] = temp;
}
int max=0;
int Q = sqrt((float)K[i])<N[i] ? sqrt((float)K[i]) : N[i];
int P = (K[i]/Q)<M[i] ? (K[i]/Q) : M[i];
for(;Q>=2&&P<=M[i];Q--,P=K[i]/Q)
{
sum[i]=0;
sum[i] += (P*(P-1)/2)*(Q*(Q-1)/2);
int L = K[i]-Q*P;
if(P>=M[i])
sum[i] += (L*(L-1)/2)*Q;
else
sum[i] += (L*(L-1)/2)*P;
max = max<sum[i] ? sum[i] : max;
}
sum[i] = max;
}
for(i=0;i<T;i++)
{
cout<<"Case #"<<i+1<<": "<<sum[i]<<endl;
}
system("PAUSE");
return 0;
}
原文：http://blog.csdn.net/dalongyes/article/details/23106163