A 牛牛分蛋糕
思路:最小化最大值用二分+贪心时间复杂度O(logn)
class Solution {
public:
/**
* 处理函数,返回在所有分法中,蛋糕数量最少的盘子中分到最多的蛋糕数量
* @param n int整型 n个盘子
* @param a int整型 a蛋糕数量
* @param b int整型 b蛋糕数量
* @return int整型
*/
int solve(int n, int a, int b) {
// write code here
int l = 1, r = a + b;
while (l < r) {
int mid = l + (r - l + 1) / 2; // 尝试答案
int ret = a / mid + b / mid; // 盘子数量
if (ret >= n) { // mid 满足条件,因为要求最大值,所以继续尝试大的答案
l = mid;
}
else {
r = mid - 1;
}
}
return l;
}
};
B 牛牛凑数字
思路:可用完成背包求具体方案来解,首先求出完全背包的最大价值,每个数字的价值为1,然后根据最大价值求具体方案
const int N = 1e6 + 5;
int f[10][N];
class Solution {
public:
/**
* 得到牛牛能够凑到的最大的数字
* @param n int整型 牛牛能够承受的价格
* @param a int整型vector 1-9这九个数字的价格数组
* @return string字符串
*/
string solve(int n, vector<int>& a)
{
// write code here
for(int i = 1; i <= 9; i ++ )
for(int j = 0; j <= n; j ++ )
{
f[i][j] = f[i - 1][j];
if(j >= a[i - 1]) f[i][j] = max(f[i][j], f[i][j - a[i - 1]] + 1);
}
if(f[9][n] == 0) return "-1";
//cout << f[9][n] << endl;
string res = "";
int j = n;
for (int i = 9; i; i --)
{
for (;;) {
if (j >= a[i -1] && f[i][j] == f[i][j - a[i -1]] + 1) {
res += to_string(i);
j -= a[i - 1];
} else {
break;
}
}
}
return res;
}
};