【笔试训练】day2

文章目录

1.牛牛的快递
- 代码：
2.最小花费爬楼梯
- 思路：
- 代码：
3.数组中两个字符串的最小距离
- 思路：
- 代码：

1.牛牛的快递

在这里插入图片描述
注意一个坑，首先就是加急是总共加5块，不是每千克加5块。
思路呃，没思路，无脑就行。

代码：


#include <iostream>
#include<algorithm>
#include<math.h>
using namespace std;

int main() {
   float a;
   char b;
    cin>>a>>b;
    int g=a-1;
    int ans=20+g;
    if(a-1-g>0)ans++;
   if(b=='y')ans+=5;
   cout<<ans;
   return 0;
}

2.最小花费爬楼梯

在这里插入图片描述

思路：

一眼dp.
起点有两种，一个是从0开始，一个是从1开始。用两个数组a,b分别维护这两种状态。

a[i]表示从起点爬到第i个阶梯最少要花费多少钱

要想爬到第i个阶梯，要么是从i-1阶梯爬过来的，要么是从i-2阶梯爬过来的。
要注意的是，题目给的cnt[i]的意思是，第i个阶梯向上爬1或者2个阶梯的费用，而不是爬1个。（没看清题目，wa了我几发，草！）。

于是容易想到状态转移方程
a[i]=min(a[i-1]+cnt[i-1],a[i-2]+cnt[i-2])
最后的a[n]就表示从起点（1）爬到第n+1（顶部）个台阶的最少花费。b[n]同理。
最后再比较一下不同的起点爬到第n个阶梯那个方法花费最少就行了。

代码：

#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N];//从1开始爬
int b[N];//从0开始爬
int c[N];//花费
int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>c[i];
    }
    a[1]=0;
    a[2]=c[1];//初始化
    for(int i=3;i<=n;i++){
        a[i]=min(a[i-1]+c[i-1],a[i-2]+c[i-2]);
    }
     b[0]=0;
     b[1]=b[0]+c[0];//初始化
    for(int i=2;i<=n;i++){
        b[i]=min(b[i-1]+c[i-1],b[i-2]+c[i-2]);
    }
    cout<<min(b[n],a[n]);
    return 0;
}

3.数组中两个字符串的最小距离

在这里插入图片描述

思路：

注意题目要求空间复杂度O(1)。先思考如果没有这个条件限制该怎么做。
无非就是用一个vector<string>把str的所有字符串找一遍，利用双指针，每找到一对str1和str2就更新一下答案，这个答案就是两个指针的距离。

不能用 vector<string>那就在每次读入的时候去处理就行了。

用两个变量存最近一次找到str1和str2的位置。再用两个变量存当前是否找到了str1和str2。
对于当前输入的str，一共有以下几种结果：

1.找到str1，记录位置
2.找到str2，记录位置
3.如果两个都找到了，就用这两个指针的距离更新答案

代码：

#include <iostream>
#include<string>
#include<algorithm>
using namespace std;

int main() {
    string a,b,c;
    int f1=0;
    int f2=0;
    int p1=0;
    int p2=0;
    int n;
    cin>>n;
    cin>>a>>b;
    
    int ans=1e9;
    for(int i=1;i<=n;i++){
        cin>>c;
        if(c==a){
            p1=i;
            f1=1;
        }else if(c==b){
            p2=i;
            f2=1;
        }

        if(f1&&f2){//两个都找到了
            ans=min(ans,abs(p2-p1));
        }
    }
   if(ans==1e9)cout<<-1;
   else cout<<ans;
    return 0;
}