时间：2014.04.05

地点：基地二楼

---------------------------------------------------------------------

一、简述

  这是2013年微软编程之美大赛资格赛的题目。

---------------------------------------------------------------------

---------------------------------------------------------------------

三、思路

  我的想法是，先对给定的点数K开根号，因为我们有限制K<=N*M，所以K在网格中总是放得下的，将K开根号后的值与N、M中的最小值做比较，如果根号值小，而当点形成一个方正时总是能获得最多矩形数，所以我们尽量向方正靠拢，于是可先计算所得方正形成的矩形数，然后将剩余的点依次往方正后面补，计算第二部分新形成的矩形数。还有一种情况是当根号值大于或等于最小边长时，这时我们不能按根号值形成方正，但可按最小边长形成一个矩形，第一部分先计算这个矩形中的矩形数，第二部分和上面一样，将余下的点数往矩形后面追加，并计算新的矩形数即可。代码如下：

#include<iostream>
#include<vector>
#include<cassert>
using namespace std;
unsigned CalculateGrid(unsigned N, unsigned M, unsigned K);
//Preconditon: N,M fail into [0,30 000] and K fail into [0,N*M]
//Postcondition: Return the max matrix numbers whitch every matrix‘s edge paralell to grid
bool CheckTheInput(unsigned N, unsigned M, unsigned K);
//Precondition: Check the parameters‘ leagal
//Postcondition: Return true when every parameter is leagal
void PrintTheResult(vector<unsigned>& vec);
//Postcondition: Print this test‘s result according to the requirements
unsigned CalculateMartrix(unsigned row, unsigned col);
//Precondition: Given a matrix
//Postcondition:Return this matrix‘s sub_matrixs number
int main()
{
	unsigned T = 0;
	cin >> T;
	assert(T >= 1 && T <= 100);

	unsigned N, M, K;
	vector<unsigned> matrix_count;
	while (T)
	{
		cin >> N>>M>>K;
		assert(CheckTheInput(N, M, K));
		matrix_count.push_back(CalculateGrid(N, M, K));
		--T;
	}
	PrintTheResult(matrix_count);
	return 0;
}
unsigned CalculateMartrix(unsigned row, unsigned col)
{
	return row*col*(row - 1)*(col - 1) / 4;
}
unsigned CalculateGrid(unsigned N, unsigned M, unsigned K)
{
	unsigned min_edge = N < M ? N : M;
	unsigned squre_root = static_cast<unsigned>(sqrt(K));
	unsigned first_part, second_part, difference;
	if (squre_root<min_edge)
	{
		first_part = CalculateMartrix(squre_root,squre_root);
		difference = K - squre_root*squre_root;
		if (difference > 1 && difference <= squre_root)
			second_part = squre_root*difference*(difference - 1) / 2;
		else if (difference == squre_root + 1)
			second_part = squre_root*squre_root*(squre_root - 1) / 2;
		else if (difference > (squre_root + 1))
			second_part = squre_root*squre_root*(squre_root - 1) / 2
			+ (difference - squre_root)*(difference - squre_root - 1) / 2;
	}
	else
	{
		unsigned row_count = K / min_edge;
		first_part = CalculateMartrix(min_edge, row_count);
		difference = K - row_count*min_edge;
		second_part = row_count*difference*(difference - 1) / 2;
	}
	return first_part + second_part;
}
bool CheckTheInput(unsigned N, unsigned M, unsigned K)
{
		return (N > 0 && N <= 30000) && (M > 0 && M <= 30000) 
			    && (K >= 1 && K <= N*M);
}
void PrintTheResult(vector<unsigned>& vec)
{
	unsigned count = 1;
	for (auto element : vec)
	{
		cout << "Case#" << count << ": " << element << endl;
		++count;
	}
}

---------------------------------------------------------------------

四、总结

微软编程之美大赛-长方形个数问题,布布扣,bubuko.com

微软编程之美大赛-长方形个数问题

原文：http://blog.csdn.net/u012333003/article/details/22983145