[笔试强训]day2

1.牛牛的快递

题目链接：牛牛的快递_牛客题霸_牛客网

思路：分小于1.0kg和大于1.0kg，其中大于1.0kg的要“向上取整” ，eg：1.7->2，2.0->2。注意一个点：第二个输入的参数是字符，要使用scanf读取的话，容易把空格读进去，eg：1.0 y,中间是有空格的，所以我们的scanf("%f%c...)是错误的，会将空格读到第二个参数里，所以在格式化输入那里加空格，或者使用cin读取。

代码：

#include <iostream>
using namespace std;

int main() 
{
    float a;
    char b;
    scanf("%f %c", &a, &b);//cin >> 也可以
    int ret = 20 + (b == 'y' ? 5 : 0);
    if (a <= 1.0)
        printf("%d", ret);
    else
    {
        int kg = a == (int)a ? a : (int)a + 1;
        ret += kg - 1;
        printf("%d", ret);
    }
}

2. 最小花费爬楼梯

题目链接：最小花费爬楼梯_牛客题霸_牛客网

思路：简单dp问题，定义好状态表示：dp[i]->到达i位置所需的最小花费，到达i位置，可由i - 1位置或者i - 2位置过来，=》状态转移方程：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])；细节问题：初始化->dp[0] = dp[1] = 0（因为一开始就可以选择从下标为0或者下标为1的位置开始爬），返回值dp[n]，因为要爬到楼梯顶部 。数据范围：length 1~10^5, val 1~10^4。用int即可（最坏的情况也就是10^9）

代码：

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

int main() 
{
    int n;
    scanf("%d", &n);
    vector<int> cost(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &cost[i]);
    vector<int> dp(n + 1);
    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;
}

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

题目链接：数组中两个字符串的最小距离__牛客网 

思路：一开始的想法是双指针

代码：

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

int main() 
{
    int n;
    string str1, str2;
    cin >> n >> str1 >> str2;
    if (!(str1.size() && str2.size()))
    {
        cout << -1;
        return 0;
    }
    vector<string> strs(n);
    for (int i = 0; i < n; i++)
        cin >> strs[i];
    int l = -1, r = 0, ret = 0x3f3f3f3f;
    while (r < n)
    {
        if ((strs[r] == str1 || strs[r] == str2) && l == -1)
        {
            l = r;
            r++;
            continue;
        }
        if ((strs[r] == str1 || strs[r] == str2) && strs[r] != strs[l])
        {
            ret = min(ret, r - l);
            l = r;
            r++;
            continue;
        }
        r++;
    }
    cout << (ret == 0x3f3f3f3f ? -1 : ret);
    return 0;

}

原来是漏了这种情况。 

代码改为：

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

int main() 
{
    int n;
    string str1, str2;
    cin >> n >> str1 >> str2;
    if (!(str1.size() && str2.size()))
    {
        cout << -1;
        return 0;
    }
    vector<string> strs(n);
    for (int i = 0; i < n; i++)
        cin >> strs[i];
    int l = -1, r = 0, ret = 0x3f3f3f3f;
    while (r < n)
    {
        if ((strs[r] == str1 || strs[r] == str2) && l == -1)
        {
            l = r;
            r++;
            continue;
        }
        if ((strs[r] == str1 || strs[r] == str2) && strs[r] != strs[l])
        {
            ret = min(ret, r - l);
            l = r;
            r++;
            continue;
        }
        if (l != -1 && strs[r] == strs[l])//这里多加一个判断
            l = r;
        r++;
    }
    cout << (ret == 0x3f3f3f3f ? -1 : ret);
    return 0;

}

解法二的思想就是贪心（dp）

代码：

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

int main() 
{
    int n;
    string str1, str2;
    cin >> n >> str1 >> str2;
    if (!(str1.size() && str2.size()))
    {
        cout << -1;
        return 0;
    }
    vector<string> strs(n);
    for (int i = 0; i < n; i++)
        cin >> strs[i];
    int ret = 0x3f3f3f3f, prev1 = -1, prev2 = -1;
    for (int i = 0; i < n; i++)
    {
        if (strs[i] == str1)
        {
            prev1 = i;
            if (prev2 != -1)
                ret = min(ret, i - prev2);
        }
        else if (strs[i] == str2)
        {
            prev2 = i;
            if (prev1 != -1)
                ret = min(ret, i - prev1);
        }
    }
    cout << (ret == 0x3f3f3f3f ? -1 : ret);
    return 0;

}