笔试专题（五）

游游的水果大礼包（枚举）

题目链接

题解

1. 枚举
2. 开始用贪心做的没想到是个错解，贪心是哪个礼包大就选哪个礼包知道这个礼包不够选，再选另一个礼包，比如反例 n = 2 m = 100 a = 3 b = 2，都选一号礼包就是3元，都选二号礼包就是4元
3. 依次枚举一号礼包的个数，再求出2号礼包的个数，1号礼包最大的数量是min(n/2,m)，2号礼包剩下的数量是min(n-2*x,(m-x)/2)
4. 其实这种题就是二元一次方程，给了x的范围，y和x有函数的关系

代码

#include <iostream>
using namespace std;

int main()
{
    int n,m,a,b;
    cin >> n >> m >> a >> b; 
    long long ans = -1;
    // 依次枚举每个1号大礼包,计算出每个2号大礼包
    for(long long i = 0;i <= min(n/2,m);i++)// 计算一号礼包的个数
    {
        // min(n-2*i,(m-i)/2) 计算2号礼包的个数
        long long sum = i*a + b * min(n-2*i,(m-i)/2);
        ans = max(ans,sum);
    }

    cout << ans << '\n';

    return 0;
}

买卖股票的最好时机(二)（贪心）

题目链接

题解

1. 贪心
只要是呈现上升趋势的就买入再卖出，这样可以获得最大的收益

代码

class Solution 
{
public:
    int maxProfit(vector<int>& prices) 
    {
       // 贪心只要股票的价格是上升趋势的就买入再卖出
       int n = prices.size();
       int sum = 0;
       for(int i = 1;i < n;i++)
       {
            if(prices[i] > prices[i-1]) 
            sum += prices[i] - prices[i-1];
       }

       return sum; 
    }
};

倒置字符串（模拟）

题目链接

题解

1. 找规律
2. 可以先将整个字符串倒置，再倒置每个单词，使用reverse函数，begin()指向开始的第一个字符，end()指向单词最后一个字符的下一个位置

代码

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

int main()
{
    string s;
    // 读入整个字符串,包含空格
    getline(cin,s);
    reverse(s.begin(),s.end());
    
    int left = 0;
    int 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 << '\n';

    return 0;
}