牛客网OJ题解--20210201
神秘餐馆
https://ac.nowcoder.com/acm/problem/21312
本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。
NC21312-神秘餐馆
题目链接
https://ac.nowcoder.com/acm/problem/21312
题目描述
一家神秘餐馆准备开放N天，牛牛 和 牛妹听到这个消息后，准备尽可能多的一起去吃午饭
餐馆有M道菜，牛牛和牛妹每次来只允许点一道菜，如果在第i天买了第j道菜
那么第i+7天也只能买第j道菜
第i天第j道菜的价格为price[i][j]
'0'-'9'代表0-9美元
'A'-'Z'代表10-35美元
'a'-'z'代表36-61美元
牛牛和牛妹一共只有budget美元，请问他们最多可以吃几天的午饭。
第一行输入3个整数n,m,budget (1 ≤ n ≤ 50, 1 ≤ m ≤ 50, 0 ≤ budget ≤ 10000)
接下来n行每行输入一个字符串，包含m个字符
第i行的第j个字符表示第i天第j道菜的价格。
测试样例
样例1
输入
7 2 13 26 14 72 39 32 85 06
输出
5
样例2
输入
8 2 20 26 14 72 39 32 85 06 91
输出
8
样例3
输入
12 4 256 Dear Code rsHa veFu nInT heCh alle ngeP hase andb ecar eful
输出
10
解题思路
实际上唯一需要注意的细节就是一旦确定了星期i吃j号菜品，那么无论以后的菜品有多贵都只能选择这个j号菜品。所以我们需要保证周i所选择的j号菜品加起来的总花费最低。比如我们看样例2，第一天周一我们肯定是选择了一号菜品花费2元，那么也就意味着第八天的周一我们只能选择一号菜品花费9元，这样算周一吃了两次一号菜品总花费11元，然而周一如果我们是根据第八天的周一菜品价格选择二号菜品，那么虽然第一天吃的是6元，但是这也意味着第八天的周一我们可以吃而号菜品1元，加起来8天内两次周一都选择的是二号菜品总花费就是7元小于11元。所以每一次我们都选择当下周i最便宜的菜品后同时要回忆以前的菜品都改成这次选择的最便宜菜品进行重新计算周i所有吃菜品j的总花费保证他是最小。至于第i天是周几，我们只需要i%7即可。
解题代码
#include <bits/stdc++.h>
using namespace std;
const int N = 55; //一次性开到最大的数组
int n, m, budget; //天数，每天的菜品数量
string s[N]; //存储一天的各个菜品价格的字符串数组
int meat[7][N]; //星期i选择第j份菜品的总花费
int cost[7]; //已知的最便宜的菜品花费
int main()
{
cin >> n >> m >> budget;
for (int i = 0; i < n; i++)
{
//记录数据并且计算出每一个字符所代表的的相对应的第i天第j份菜品的费用
cin >> s[i];
for (int j = 0; j < m; j++)
{
if (s[i][j] >= '0' && s[i][j] <= '9')
s[i][j] = s[i][j] - '0';
if (s[i][j] >= 'A' && s[i][j] <= 'Z')
s[i][j] = s[i][j] - 'A' + 10;
if (s[i][j] >= 'a' && s[i][j] <= 'z')
s[i][j] = s[i][j] - 'a' + 36;
}
}
//已知的最省钱的花费
int money = 0;
//统计n天的最多吃饭次数
for (int i = 0; i < n; i++)
{
//计算前先减掉这次菜品组合，比如样例2中的星期1我们
//优先选择了花费小的菜品1(即此时会吃两次菜品2花费分
//别是（2,9），那么现在到了第8天即又到
//了周一我们假设现在有更好的更省钱的菜品组合
//（后面确实有更好的即周一时 选择菜品2（6,1），
//所以减去之前的花费（2,9）重新统计星期i的选餐组合
money -= cost[i % 7];
for (int j = 0; j < m; j++)
{
//统计选择了第j件菜品时所有吃第j个菜品的花费
meat[i % 7][j] += s[i][j];
}
//假设选择每天的第一个菜品吃最省钱
cost[i % 7] = meat[i % 7][0];
for (int j = 1; j < m; j++)
{
//统计若选择吃第j件菜品是否比选择吃第1件菜品更省钱
cost[i % 7] = min(cost[i % 7], meat[i % 7][j]);
//保证每一次选择的都一定是一直当前的最省钱组合
}
money += cost[i % 7];
if (money > budget)
{
//在餐厅关闭前花完钱了，那么返还吃了几次
cout << i << endl;
system("pause");
return 0;
}
}
//如果花完钱之前餐厅关闭了，那么必定每天都吃了一次，返还n
cout << n << endl;
system("pause");
return 0;
} NC21842-正方形检测
题目链接
https://ac.nowcoder.com/acm/problem/21842
题目描述
给你平面直角坐标系中的四个点，判断这四个点是否构成一个正方形 。
第一行输入四个整数xix_ixi (0≤xi≤100000 \le x_i \le 100000≤xi≤10000)
第二行输入四个整数yiy_iyi (0≤yi≤100000 \le y_i \le 100000≤yi≤10000)
测试样例
样例1
输入
0 0 2 2 0 2 0 2
输出
It's a square
样例2
输入
0 1 5 6 1 6 0 5
输出
It's a square
样例3
输入
0 0 7 7 0 3 0 3
输出
Not a square
解题思路
实际上是一个规律，只要满足就一定是正方形，可以牢记，规律就是如下图所示：
只有当为正方形时，不重复的对每一个点进行连边，最后我们会得到6条边，进行从小到大排序：a表示一条直角边长度
所以我们使用双重循环判断可以发现刚好6个边可以组成7个相等长度的情况。即
由此就可以判断出结果了。注意不能用有四条边等于a的条件判断，这种条件有bug。
解题代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x1, x2, x3, x4;
int y1, y2, y3, y4;
cin >> x1 >> x2 >> x3 >> x4;
cin >> y1 >> y2 >> y3 >> y4;
int length[7];
length[1] = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
length[2] = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3);
length[3] = (x1 - x4) * (x1 - x4) + (y1 - y4) * (y1 - y4);
length[4] = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3);
length[5] = (x2 - x4) * (x2 - x4) + (y2 - y4) * (y2 - y4);
length[6] = (x3 - x4) * (x3 - x4) + (y3 - y4) * (y3 - y4);
sort(length + 1, length + 7);
int num = 0;
for (int i = 1; i < 7; i++)
{
for (int j = i + 1; j < 7; j++)
{
if (length[i] == length[j])
{
num++;
}
}
}
if (num == 7)
{
cout << "It's a square" << endl;
}
else
cout << "Not a square" << endl;
system("pause");
return 0;
}
投递京东等公司10个岗位