免费试用网站怎么做,手机建站源码,法治建设网站模块名称,wordpress如何添加安装导航T1 牛牛的快递 原题链接#xff1a;牛牛的快递_牛客题霸_牛客网 (nowcoder.com) 题目类型#xff1a;模拟 审题确定思路#xff1a;
1、超过1kg和不足1kg有两种不同收费方案 ---- 起步价问题
2、超出部分不足1kg的按1kg计算 ----- 向上取整
3、向上取整的实现思路…T1 牛牛的快递 原题链接牛牛的快递_牛客题霸_牛客网 (nowcoder.com) 题目类型模拟 审题确定思路
1、超过1kg和不足1kg有两种不同收费方案 ---- 起步价问题
2、超出部分不足1kg的按1kg计算 ----- 向上取整
3、向上取整的实现思路
a使用库函数ceil() //要包含头文件 #inlcudecmath
b:强转 判断
if(ch - (int)ch 0) // eg: (int)1.5 1
//说明需要向上取整
参考代码
#include iostream
#include cmath
using namespace std;int main() {float a;char b;cin ab;if(a 1){int ret ceil(a)-1;cout(b y ? 25ret : ret20)endl;}else {cout (b y ? 25: 20)endl;}return 0;
} T2最小花费爬楼梯 原题链接最小花费爬楼梯_牛客题霸_牛客网 (nowcoder.com)
题目类型dp 审题确定思路
1、确定状态表示dp[i]表示 以i位置为结尾从0或1下标开始到这个位置的最小花费
2、确定状态转移方程以i位置为结尾进行思考。因为可以选择跳一层或者两层说明当站在i这层位置的时候可能是从前一层或者前两层跳上来的。要使得当前i位置的花费最小则要对比从前一层跳过来的最低花费和从前两层跳过来的最低花费 谁更小 再加上往上跳对应要支付的花费就得到当前层最低花费
其中最低花费对应状态表示dp[i]
将上述关系转化为代码
dp[i] min(dp[i-1] cost[i-1] ,dp[i-2]cost[i-2]); 3、确定填表顺序
因为需要用到前两层的dp信息所以从左往右填表 4、处理边界情况
因为下标从0开始可以从0也可以从1开始跳而刚站上这层楼梯时是不需要花费的往上跳才需要支付这层的花费。所以dp[0]和dp[1]都为0
接着填表从i 2开始就不会发生越界问题。 参考代码
#include iostream
#includevector
#includecmath
using namespace std;int main() {int n;cinn;vectorintcost(n);for(int i 0;in;i){cincost[i];}vectorintdp(n1);dp[0] 0;dp[1] 0;for(int i 2;in;i){dp[i] min(dp[i-1] cost[i-1] ,dp[i-2]cost[i-2]);}coutdp[n];return 0;}T3数组中两个字符串的最小距离 原题链接数组中两个字符串的最小距离__牛客网 (nowcoder.com)
题目类型贪心、字符串 审题确定思路
1、题目说的strs其实是个字符串类型的数组里面存放的都是字符串
2、暴力解法先固定一个字符串str1然后再搜索str2计算两个字符串间的距离并与记录的最短距离进行比较
3、优化思路贪心 ---- 使用一个或多个变量来表示前驱的信息即预处理信息。最终达到优化一层循环的效果
4、优化实现方法设置两个int变量prev1 和 prev2 分别记录str1和str2最后一次出现的下标。
5、优化效果可以不用创建字符串数组来记录strs中的字符串而是直接用一个字符串来模拟当前遍历到的strs字符串数组中的字符串。因为prev1 和 prev2 这两个变量已经记录了信息strs遍历完的元素不会再次遍历所以可以省去构建数组的这一步。 参考代码
#include iostream
#includevector
#includecmath
using namespace std;int main() {//处理输入信息string str1 ,str2;int n;cin nstr1str2;//使用一个字符串变量来表示当前遍历到的字符串string s;//设置变量记录前驱信息优化一层循环//初始化为-1是为了区别str1/str2是否在strs中出现int prev1 -1,prev2 -1;//ret 记录两字符串间的最短距离为不影响最短距离的比较所以设置个较大值//0x3f3f3f3f是常用数据可近似看做无限大值int ret 0x3f3f3f;for(int i 0;in;i){cin s;if(s str1){prev1 i;if(prev2 ! -1)ret fmin(ret,abs(prev2 - prev1));}else if(s str2) //要写出 s str2 不能直接写else if因为除了str1和str2strs中的字符串即s还有其他样式的{prev2 i;if(prev1 ! -1)ret fmin(ret,abs(prev2 - prev1));}}//判断是否str1和str2都在strs中出现了if(ret ! 0x3f3f3f){cout retendl;}else {cout-1endl;}return 0;}
