T1 牛牛的快递
原题链接：牛牛的快递_牛客题霸_牛客网 (nowcoder.com)
题目类型：模拟
审题&确定思路：
1、超过1kg和不足1kg有两种不同收费方案 ---- 起步价问题
2、超出部分不足1kg的按1kg计算 ----- 向上取整
3、向上取整的实现思路
a：使用库函数ceil() //要包含头文件 #inlcude<cmath>
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 >>a>>b;
if(a >1)
{
int ret = ceil(a)-1;
cout<<(b == 'y' ? 25+ret : ret+20)<<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>
#include<vector>
#include<cmath>
using namespace std;
int main() {
int n;
cin>>n;
vector<int>cost(n);
for(int i = 0;i<n;i++)
{
cin>>cost[i];
}
vector<int>dp(n+1);
dp[0] = 0;
dp[1] = 0;
for(int i =2;i<=n;i++)
{
dp[i] = min(dp[i-1] +cost[i-1] ,dp[i-2]+cost[i-2]);
}
cout<<dp[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>
#include<vector>
#include<cmath>
using namespace std;
int main() {
//处理输入信息
string str1 ,str2;
int n;
cin >>n>>str1>>str2;
//使用一个字符串变量来表示当前遍历到的字符串
string s;
//设置变量记录前驱信息，优化一层循环
//初始化为-1是为了区别str1/str2是否在strs中出现
int prev1 = -1,prev2 = -1;
//ret 记录两字符串间的最短距离，为不影响最短距离的比较，所以设置个较大值
//0x3f3f3f3f是常用数据，可近似看做无限大值
int ret = 0x3f3f3f;
for(int i = 0;i<n;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和str2，strs中的字符串（即s）还有其他样式的
{
prev2 = i;
if(prev1 != -1)ret = fmin(ret,abs(prev2 - prev1));
}
}
//判断是否str1和str2都在strs中出现了
if(ret != 0x3f3f3f)
{
cout << ret<<endl;
}
else
{
cout<<-1<<endl;
}
return 0;
}
