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;
}