​​​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，故贪心是不可取的。

题解： 正确的解法是，枚举所有可能的情况，返回最大值。

代码：

#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。

题解一：动态规划

题解二： 贪心，只有股票利润有上升，就给它拿下。

代码：

#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多次逆序

代码：

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