上海计算机学会2021年9月月赛C++丙组T3股票市场_股票市场 上海月赛c++

题目描述

小爱知道一只股票在今后 n 天的价格。在第一天开始前，小爱有 m 元，那么在最后一天结束后，她最多能有多少钱呢？小爱每天都可以买入或卖出股票，注意股票在交易时的最小单位为 1 股。例如当有 13 元的时候，若股价为 4 元一股，则最多只能买 3 股。

规定每天只能交易一次，如果当天已经买入股票，就不能卖出，反之，如果当天已经卖出，则不能再买进股票。

输入格式

第一行：两个整数，表示 n 和 m；
第二行：n 个整数 a1​,…,an​，表示每天的股票价格。

输出格式

单个整数：表示能获得的最大钱数。

数据范围

• 1≤m≤100；
• 1≤ai​≤100；
• 对于 30% 的数据，1≤n≤20；
• 对于 60% 的数据，1≤n≤5,000；
• 对于 100% 的数据，1≤n≤100,000；
• 保证输出答案不超过 10^18。

样例数据

输入:
3 10
1 2 3
输出:
30
说明:
第一天以1元的价格买进10股，到了最后一天以3元的价格卖出，10元变成了30元
输入:
4 100
40 20 10 5
输出:
100
说明:
没有买股票
输入:
6 100
1 2 10 1 5 10
输出:
10000
解析：贪心算法，如果明天涨价，买入，如果明天降价，卖出。

#include <bits/stdc++.h>
using namespace std;
int a[1000005];
 
int main()
{
    int n,m;
    cin>>n>>m;
    int g=0;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for (int i=1;i<=n;i++)
    {
        if (a[i+1]<a[i])//降价，买入
        {
            m=m+g*a[i];
            g=0;
        }else if (a[i+1]>a[i])//涨价，卖出
        {
            g+=m/a[i];
            m=m%a[i];
        }
    }
    cout<<m<<endl;
    return 0;
}