牛客编程巅峰赛S1第4场 - 黄金&钻石
A-牛牛分蛋糕
链接：https://ac.nowcoder.com/acm/contest/6384/A
来源：牛客网
牛牛今天家里要来客人，所以牛牛今天特意做了他最拿手的两种蛋糕，但是他是一个有洁癖的人，所以他在分蛋糕时，有如下几个原则：
1.他不希望一个盘子里出现两种蛋糕
2.他希望每个盘子中都有蛋糕
3.他想让装有最少蛋糕数量的盘子中装有的蛋糕数量尽可能多
C++(暴力做法)
遍历分配给a和b的盘子数量，计算出他们分配的盘子中蛋糕的最小值，然后给res赋值求最大值
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 res=0;
for(int i=1;i<n;i++)
{
int amin=a/i;
int bmin=b/(n-i);
res=max(res,min(amin,bmin));
}
return res;
}
};
C++（二分做法）
二分盘子中最少蛋糕的数量，check中将a，b一个个往盘子里放，如果可以分配那么
class Solution {
public:
/**
* 处理函数，返回在所有分法中，蛋糕数量最少的盘子中分到最多的蛋糕数量
* @param n int整型 n个盘子
* @param a int整型 a蛋糕数量
* @param b int整型 b蛋糕数量
* @return int整型
*/
bool check(int mid, int n, int a, int b) {
for (int i = 1; i <= n; i++) {
if (a >= mid) a -= mid;
else if (b >= mid) b -= mid;
else return false;
}
return true;
}
int solve(int n, int a, int b) {
// write code here
int l = 1, r = min(a , b);
int ans = 0;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid, n, a, b))
l = (ans = mid) + 1;
else
r = mid - 1;
}
return ans;
}
};
B-牛牛凑数字
链接：https://ac.nowcoder.com/acm/contest/6384/B
来源：牛客网
牛牛今天逛商店，看到商店里摆着一些很漂亮的数字，牛牛非常喜欢，想买一些数字带回家。
数字一共有九种类型，分别是1-9这九个数字，每个数字的价钱都不一样，而且每个数字的货源都非常充足。
牛牛是个完美主义者，他希望用自己的能够承受的价格，从这些数字里面购买，并且凑到最大的数字带回家。
备注：
第一个参数为一个整数n(0 ≤ n ≤ 106)，代表牛牛所能承受的价格。
第二个参数为1-9这九个数字的价格数组，a1,a2,……,a9(1≤ ai ≤105)。
程序应返回:一个数字，代表牛牛能凑到的最大的数字。当然，如果牛牛一个数字都买不起，返回"-1"即可。
注意，由于数字可能会很大，所以程序中需要处理成string类型进行返回。
C++：
首先要了解一个点，数字越长，那么数字越大，所以是往多了买。那么买了之后余下来下来的那么几块钱，应该往大了买。
接着就是一个模拟的过程，先找到最小值，这样n/minn就是该数目得最大长度。然后求出全买最小值之后得余数。每次找的数字应该是余数+最小值中得最大值，所以从9-id找。
class Solution
{
public:
/**
* 得到牛牛能够凑到的最大的数字
* @param n int整型 牛牛能够承受的价格
* @param a int整型vector 1-9这九个数字的价格数组
* @return string字符串
*/
string s;
string solve(int n, vector<int>& a)
{
// write code here
int id,minn=999999999;
for(int i=0; i<a.size(); i++)
{
if(a[i]<=minn)
{
minn=a[i];
id=i+1;
}
}
//printf("%d %d",minn,id);
int modd=n%minn;
//printf("%d %d %d %d\n",minn,n,n/minn,modd);
for(int i=0; i<n/minn; i++)
{
int x=modd+minn;
//printf("%d ",i);
for(int j=9; j>=id; j--)
{
if(x>=a[j-1])
{
s+=j+'0';
modd=x-a[j-1];
break;
}
}
}
if(s=="")
return "-1";
else
return s;
}
};
C-牛妹的野菜
链接：https://ac.nowcoder.com/acm/contest/6384/C
来源：牛客网
书接上回，牛妹组织春游，有一个有趣的项目是挖番薯。聪明的牛妹拿到了一个表明了番薯洞的地图，每个番薯洞中有一定数量的番薯。同时，我们知道番薯洞的连接路径，并规定路径是单向且小序号指向大序号，也无环。可以从任意一处开始挖，然后沿着连接往下挖（仅能选择一条路径），当无连接时，结束。
设计一种挖番薯的方案，使得可以挖到更多的番薯。
输出路径。
一个记忆路径的dp做法，pos保存的是最大的dp的下标pre保存的是上一个，也就是这个数字是从哪里过来的。
先把全部的路径存入vector构成图；然后再写一个动态转化的dp，dp[v[i][j]]=max(dp[i],dp[v[i][j]]);标记pre。
class Solution
{
public:
/**
*
* @param potatoNum int整型vector 依次表示序号为1,2,3..的番薯洞各有多少个番薯
* @param connectRoad int整型vector<vector<>> 每个一维数组[x,y]表示从第x号番薯洞到第y号有路
* @return string字符串
*/
int dp[305]= {0};
int pre[305]={0};
string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad)
{
// write code heres
vector<int>v[305];
int pos=1;
for(int i=0; i<connectRoad.size(); i++)
{
int t1=connectRoad[i][0];
int t2=connectRoad[i][1];
v[t1].push_back(t2);
}
for(int i=1;i<=potatoNum.size();i++)
{
dp[i]+=potatoNum[i-1];
if(dp[pos]<dp[i])
pos=i;
for(int j=0;j<v[i].size();j++)
{
if(dp[v[i][j]]<dp[i])
{
dp[v[i][j]]=dp[i];
pre[v[i][j]]=i;
}
}
}
string ans=to_string(pos);
pos=pre[pos];
while(pos!=0){
ans=to_string(pos)+'-'+ans;
pos=pre[pos];
}
return ans;
}
};
推荐阅读