首页 > 代码库 > Codeforces Round #257 (Div. 2)C 贪心
Codeforces Round #257 (Div. 2)C 贪心
Jzzhu has a big rectangular chocolate bar that consists of n?×?m unit squares. He wants to cut this bar exactly k times. Each cut must meet the following requirements:
- each cut should be straight (horizontal or vertical);
- each cut should go along edges of unit squares (it is prohibited to divide any unit chocolate square with cut);
- each cut should go inside the whole chocolate bar, and all cuts must be distinct.
The picture below shows a possible way to cut a 5?×?6 chocolate for 5 times.
Imagine Jzzhu have made k cuts and the big chocolate is splitted into several pieces. Consider the smallest (by area) piece of the chocolate, Jzzhu wants this piece to be as large as possible. What is the maximum possible area of smallest piece he can get with exactlyk cuts? The area of a chocolate piece is the number of unit squares in it.
A single line contains three integers n,?m,?k (1?≤?n,?m?≤?109; 1?≤?k?≤?2·109).
Output a single integer representing the answer. If it is impossible to cut the big chocolate k times, print -1.
3 4 1
6
6 4 2
8
2 3 4
-1
In the first sample, Jzzhu can cut the chocolate following the picture below:
In the second sample the optimal division looks like this:
In the third sample, it‘s impossible to cut a 2?×?3 chocolate 4 times.
题解
好逗的题目。就是一个网格状的物品,n行m列,笔直直的切k刀,问所有的可能性中,最大的,每次切出来的结果最小的块的大小。
自己瞎贪心跪了。赛后发现其实可以枚举可能的在行这个方向切得刀数r,计算列方向切的刀数o,然后更新答案的方法。当然,枚举的时候也是只枚举因数,这样就可以把复杂度从O(N)降到O( sqrt(N) )。中间在加上一些优化,然后就没事了。
代码示例
/****************************************************************************** * COPYRIGHT NOTICE * Copyright (c) 2014 All rights reserved * ----Stay Hungry Stay Foolish---- * * @author :Shen * @name :C * @file :G:\My Source Code\【ACM】比赛\0719 - CF\C.cpp * @date :2014/07/19 20:57 * @algorithm :Greedy ******************************************************************************/ #include <bits/stdc++.h> using namespace std; template<class T>inline bool updateMin(T& a, T b){ return a > b ? a = b, 1 : 0; } template<class T>inline bool updateMax(T& a, T b){ return a < b ? a = b, 1 : 0; } typedef long long int64; int64 n, m, k, ans; int64 run() { if (n - 1 + m - 1 < k) ans = -1; for (int64 i = 1; i <= n; i++) { int64 r = n / (n / i); i = r; if (k - (r - 1) > m - 1) continue; int64 o = max(k - (r - 1) + 1, 1LL); updateMax(ans, 1LL * (n / r) * (m / o)); } return ans; } int main() { cin >> n >> m >> k; cout << run() << endl; return 0; }
Codeforces Round #257 (Div. 2)C 贪心