首页 > 代码库 > CodeForces 449A - Jzzhu and Chocolate
CodeForces 449A - Jzzhu and Chocolate
传送门：Jzzhu and Chocolate
题意：
给出一个N * M的矩阵，给K个操作，每次操作可以横/竖切割矩阵，最后求K次切割之后，矩阵最小的那块面积最大是多少？
分析：
按照题意，题目求的结果是：（最小的面积，最大是多少），那么可以想到，K次切割之后尽量使得每个块的面积相等，某些块比较大（因为不一定能平均分），那么就可以使得最小的那块面积最大了。
然后如何切割呢？
因为有横竖两个切割方法，那么我们可以设X为横切割数，Y为竖切割数，其中（0 <= X, Y <= K）,因为最多对一个方向切割K次，最少不切割，就是0了。这个范围很重要。
按照上面分析的， （K次切割之后尽量使得每个块的面积相等），首先只对其中一个方向来看，尽量相等，那么我们可以不管剩下不想等的了，因为肯定比其他大，就不是我们想要的最小那块，那么根据整除的性质，设最后横竖剩下的那块大小为A * B， 那么就有
A = N / (X + 1); (为什么是X + 1, 因为切了X次之后，就肯定有X+1份，那么求平均大小，就是除X+1咯)
B = M / (Y + 1);
注意，上面是整除，也可以写成：
A = floor(N / (X + 1));
B = floor(M / (Y + 1));
那么得到A * B 最大，就是
=> A * B = floor(N / (X + 1)) * floor(M / (Y + 1)); 最大
暂时忽略整除性质（这个很重要，但是推导公式的时候，可以先忽略，因为不会影响推导）。
=> A * B = N / (X + 1) * M / (Y + 1);
要使得上面A * B 最大，那么就是 N / (X + 1) * M / (Y + 1) 最大就好了
=> A * B = (N * M) / ((X + 1) * (Y + 1))
因为N, M为已知数，使得方程组最大，分子固定，那么只需要分母最小就好了。
现在就转化成为求(X + 1) * (Y + 1)如何情况下最小。
因为X + Y == K，这里可以看出来，横竖必须要满足可以切割K次
而又因为假如有N个格子，最多切N - 1次，所以可以得到判定式
=> 如果 （N - 1 + M - 1 < K） 那么最后是切不完的，结果就是 -1
由(X + 1) * (Y + 1)， X + Y == K可以得到，新的方程式是：
=> (X + 1) * (K - X + 1)
设F（X）= (X + 1) * (K - X + 1) 最小，现在就是求F（X）最小的问题了，
=> F（X） = -X ^ 2 + K * X + K + 1 （0 <= X <= K）（0 <= X <= N）
这个是一元二次方程组，其中K为已知（题目给了）
最后就是求解这个方程组的最小值问题了。
学过数学的都知道，这个方程组的开口向下
由于X的范围是[0， K]，现在要讨论K与N的关系了
（1） 如果 K <= N - 1（为什么是N - 1, 因为如果要把一个面切成N份，只需要切N-1次就可以了），那么就是可以在N上切K次，
由于方程式的性质（开头向下的一元二次方程），那么容易想到要使得F（X）最小，只有两个点，
1. X == 0 这个时候F（X）跟y轴相交
2. 因为对于X，F（X）在y轴线右边是单调递减的，所以如果要使得F（X）最小，X取最大值就可以了，所以X == K
那么第一种情况下，X == K就是解（简单吧？）
X == K的话，那么Y == 0 咯
所以A * B == floor(N / (K + 1)) * floor(M / (0 + 1))；
因为现在假设的是横切K次，有可能列切K次才是最优结果，那么就做两次再对比咯
A * B == floor(M / (K + 1)) * floor(N / (0 + 1))；
两个结果取最大值就行了。
（2） 如果 K > N - 1，那么就要讨论如何切割了。
还是那个方程式 F（X） = -X^2 + K * X + K + 1 （0 <= X <= K）（0 <= X <= N）
1. X == 0 这个时候F（X）跟y轴相交
2. 因为对于X，F（X）在y轴线右边是单调递减的，所以如果要使得F（X）最小，X取最大值就可以了，最大值就是N，但是不能切N次，所以取N - 1 （N - 1次就可以把整块切成N份了）
那么第二种情况下，X == N - 1就是解
X == N - 1的话，那么Y == K - （N - 1） 咯
所以A * B == floor(N / ((N - 1) + 1)) * floor(M / ((K - (N - 1)) + 1))；
因为现在假设的是横切K次，有可能列切K次才是最优结果，那么就做两次再对比咯
A * B == floor(M / ((M - 1) + 1)) * floor(N / ((K - (M - 1)) + 1))；
两个结果取最大值就行了。
代码如下：
1 #ifndef ONLINE_JUDGE 2 #define __DEBUG__ 0 3 #endif 4 5 /* 6 * ======================================= 7 * FileName: code.cpp 8 * Desc: 9 * Author: vinceliang 10 * Email: liangguoqiu@gmail.com 11 * HomePage: 12 * Version: 0.0.1 13 * LastChange: 2014-07-15 12:16:49 14 * History: 15 *======================================== 16 */ 17 18 19 20 #ifdef __DEBUG__ 21 #define Log(...) printf(__VA_ARGS__) 22 #else 23 #define Log(...) // 24 #endif 25 26 #include <algorithm> 27 #include <string> 28 #include <complex> 29 #include <cassert> 30 #include <memory> 31 #include <set> 32 #include <stack> 33 #include <map> 34 #include <list> 35 #include <deque> 36 #include <numeric> 37 #include <cctype> 38 #include <cstddef> 39 #include <vector> 40 #include <queue> 41 #include <iostream> 42 #include <iomanip> 43 #include <iterator> 44 #include <cmath> 45 #include <cstdio> 46 #include <cstdlib> 47 #include <sstream> 48 #include <fstream> 49 #include <ctime> 50 #include <cstring> 51 #include <functional> 52 #include <bitset> 53 54 using namespace std; 55 56 #if defined(_MSC_VER) || defined(__BORLANDC__) 57 typedef unsigned __int64 uint64; 58 typedef unsigned __int64 ULL; 59 typedef signed __int64 int64; 60 typedef signed __int64 LL; 61 #else 62 typedef unsigned long long uint64; 63 typedef unsigned long long ULL; 64 typedef signed long long int64; 65 typedef signed long long LL; 66 #endif 67 68 typedef vector<int> VI; 69 typedef vector<string> VS; 70 typedef pair<int, int> PII; 71 typedef pair<int64, int64> PLL; 72 typedef vector<int64> VL; 73 74 #define pb push_back 75 #define pob pop_back 76 #define mp make_pair 77 #define fi first 78 #define se second 79 80 #define PII pair< int,int > 81 #define PSS pair< string,string > 82 #define PDD pair< double,double > 83 #define PLL pair< LL, LL > 84 85 #define FOR( i, a, b ) for ( int i=(a), _n=(b); i < _n; ++i ) 86 #define FORE( i, a, b ) for ( int i=(a), _n=(b); i <= _n; ++i ) 87 #define FORD( i, a, b ) for ( int i=(a), _n=(b); i >= _n; --i ) 88 89 #define REP( i, n ) FOR( i, 0, (n) ) 90 #define REPE( i, n ) FORE( i, 1, (n) ) 91 92 #define ALL( c ) (c).begin(), (c).end() 93 #define SORT( c ) sort( ALL( c ) ) 94 #define LEN( s ) (int)( (s).size() ) 95 #define CLS( a ) memset( (a),0,sizeof(a) ) 96 97 #define IOS ios::sync_with_stdio( false ) 98 99 const double PI = 3.1415926535897932384626433832795028841971;100 const double EPS = 1E-9;101 const int64 INF64 = (int64)1E18;102 const int INF = 1 << 30;103 const int maxn = 1005;104 105 LL fun( LL iMax, LL iMin, LL k )106 {107 LL Area = -1;108 if ( iMax > k ) 109 {110 Area = ( iMax / (k + 1) ) * iMin;111 }112 else 113 {114 LL leftK = k - (iMax - 1);115 if ( iMin > leftK )116 {117 Area = ( iMin / ( leftK + 1 ) );118 }119 else120 {121 Area = -1;122 }123 }124 return Area;125 }126 127 void run()128 {129 LL n, m, k;130 while ( cin >> n >> m >> k )131 {132 133 LL Area = fun( n, m, k );134 LL Area2 = fun( m, n, k );135 if ( Area2 > Area ) Area = Area2;136 cout << Area << endl;137 138 }139 140 }141 142 143 int main( int argc, char **argv )144 {145 146 #ifndef ONLINE_JUDGE147 freopen("in.txt", "r", stdin);148 // freopen("out.txt", "w", stdout);149 #endif150 151 time_t st = clock();152 153 run();154 155 Log("\n=============\n");156 Log("Time: %.2lf sec\n", (clock() - st) / double(CLOCKS_PER_SEC));157 158 return 0;159 160 }
CodeForces 449A - Jzzhu and Chocolate