48days强训——day11
第一题： 游游的水果大礼包
链接：游游的水果大礼包
题目描述 游游有nnn个苹果，mmm个桃子。她可以把2个苹果和1个桃子组成价值aaa元的一号水果大礼包，也可以把1个苹果和2个桃子组成价值bbb元的二号水果大礼包。游游想知道，自己最多能组成多少价值总和的大礼包？ 输入描述: 四个正整数n,m,a,bn,m,a,bn,m,a,b，用空格隔开。分别代表苹果的数量、桃子的数量、一号大礼包价值、二号大礼包价值。 1≤n,m,a,b≤1061\leq n,m,a,b\leq 10^61≤n,m,a,b≤106 输出描述: 一个整数，代表大礼包的最大价值总和。 示例1 输入 3 4 1 2 输出 4 说明 组成两个二号水果大礼包，使用了2个苹果和4个桃子。总价值为4。 示例2 输入 1 1 5 6 输出 0 说明 显然无法组合成任意一个大礼包
错误题解：起初想到的是贪心，但是贪心这一题不适用。n=2，m=100，a=2，b=3时，贪心值为2，而最大价值为6，故贪心是不可取的。
题解： 正确的解法是，枚举所有可能的情况，返回最大值。
代码：
代码语言：javascript代码运行次数：0运行复制#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n,m,a,b;
cin >> n >> m >> a >> b;
long long ret = 0;
for(long long x = 0;x <= min(n/2,m);x++)
{
long long y = min(n - 2 * x,(m - x) / 2);
ret = max(ret,a*x + b*y);
}
cout << ret << endl;
return 0;
}第二题：买卖股票的最好时机
链接：买卖股票的最好时机(二)_牛客题霸_牛客网
描述 假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益 1. 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票 2. 如果不能获取收益，请返回0 3. 假设买入卖出均无手续费 数据范围： 0≤n≤1×1050≤n≤1×105 ， 1≤prices[i]≤1041≤prices[i]≤104 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n) 进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n) 输入描述： 第一行输入一个正整数 n ，表示数组 prices 的长度 第二行输入 n 个正整数，表示数组中prices的值 输出描述： 输出最大收益 示例1 输入： 7 8 9 2 5 4 7 1 输出： 7 说明： 在第1天(股票价格=8)买入，第2天(股票价格=9)卖出，获利9-8=1 在第3天(股票价格=2)买入，第4天(股票价格=5)卖出，获利5-2=3 在第5天(股票价格=4)买入，第6天(股票价格=7)卖出，获利7-4=3 总获利1+3+3=7，返回7 示例2 输入： 5 5 4 3 2 1 输出： 0 说明： 由于每天股票都在跌，因此不进行任何交易最优。最大收益为0。 示例3 输入： 5 1 2 3 4 5 输出： 4 说明： 第一天买进，最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。
题解一：动态规划
题解二： 贪心，只有股票利润有上升，就给它拿下。
代码：
代码语言：javascript代码运行次数：0运行复制#include <bits/stdc++.h>
using namespace std;
//动态规划
int main()
{
int n;
cin >> n;
vector<int> p(n + 1);
for (int i = 0; i < n; i++) cin >> p[i];
vector<int> f(n);
auto g = f;
f[0] = -p[0];
g[0] = 0;
for (int i = 1; i < n; i++)
{
f[i] = max(f[i - 1], g[i - 1] - p[i]);
g[i] = max(g[i - 1], f[i - 1] + p[i]);
}
cout << g[n - 1];
return 0;
}
//贪心
int main()
{
int n;
cin >> n;
vector<int> p(n + 1);
for (int i = 0; i < n; i++) cin >> p[i];
int ret = 0;
for(int i = 1;i < n;i++)
{
if(p[i] > p[i-1]) ret +=p[i]-p[i-1];
}
cout << ret << endl;
return 0;
}第三题：倒置字符串
链接：倒置字符串_牛客题霸_牛客网
描述 将一句话的单词进行倒置，标点不倒置。比如 I like beijing. 经过函数后变为：beijing. like I 输入描述： 每个测试输入包含1个测试用例： I like beijing. 输入用例长度不超过100 输出描述： 依次输出倒置之后的字符串,以空格分割 示例1 输入： I like beijing. 输出： beijing. like I
题解一：利用栈的先进先出的特性。
题解二： 利用reserve多次逆序
代码：
代码语言：javascript代码运行次数：0运行复制#include <bits/stdc++.h>
using namespace std;
//利用栈
int main()
{
stack<string> st;
string s;
while (cin >> s)
{
st.push(s);
}
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
return 0;
}
//利用reserve多次逆序
int main()
{
string s;
getline(cin,s);
reverse(s.begin(),s.end());
int left = 0,n = s.size();
while(left < n)
{
int right = left;
while (right < n && s[right] != ' ')
{
right++;
}
reverse(s.begin()+left, s.begin()+right);
//跳过空格
while (right<n && s[right] == ' ')right++;
left = right;
}
cout << s <<endl;
return 0;
}
发布评论