CSU2026 Daydreaming Stockbroker（贪心）

Daydreaming Stockbroker

Time Limit: 1 Sec
Memory Limit: 512 Mb
Submitted: 67
Solved: 20

Description

Gina Reed, the famous stockbroker, is having a slow day at work, and between rounds of solitaire she is daydreaming. Foretelling the future is hard, but imagine if you could just go back in time and use your knowledge of stock price history in order to maximize your profits!

Now Gina starts to wonder: if she were to go back in time a few days and bring a measly $100 with her, how much money could she make by just buying and selling stock in Rollercoaster Inc. (the most volatile stock in existence) at the right times? Would she earn enough to retire comfortably in a mansion on Tenerife?

Note that Gina can not buy fractional shares, she must buy whole shares in Rollercoaster Inc. The total number of shares in Rollercoaster Inc. is 100 000, so Gina can not own more than 100 000 shares at any time. In Gina’s daydream, the world is nice and simple: there are no fees for buying and selling stocks, stock prices change only once per day, and her trading does not influence the valuation of the stock.

Input

The first line of input contains an integer d (1 ≤ d ≤ 365), the number of days that Gina goes back in time in her daydream. Then follow d lines, the i’th of which contains an integer pi (1 ≤ pi ≤ 500) giving the price at which Gina can buy or sell stock in Rollercoaster Inc. on day i. Days are ordered from oldest to newest.

Output

Output the maximum possible amount of money Gina can have on the last day. Note that the answer may exceed $2^{32}$.

Sample Input

Sample Output

链接

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2026

题意

给你接下来n天的股票价格，每天可以买入或者卖出多股，问n天之后最大的收益（包括最开始的钱），假设最开始有100元。

题解

没有了交易只能为1份的“限制”，不过还是低价买入高价卖出的贪心做法。遍历找到一个连续的最低价格买入，遇到高价就卖出，但是后面可能会有更高的价格卖出，所以需要记录上一次交易的价格和数量，到一个更高的价格再次交易，相当于上次没有交易。100 200 300 ，(200 - 100) * num + (300 -200) * num = (300-200+200-100) * num。

代码

Status	Accepted
Memory	2024kB
Length	640

// money当前拥有总价值，curprice记录当前交易价格，number记录可购买的升值股数
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;

int main()
{
    int n;
    scanf("%d", &n);
    ll money = 100, curprice = 100, number = 0, x = 0;
    for (int i = 0; i < n; ++i)
    {
        scanf("%lld", &x);
        if (x <= curprice) // 低价
        {
            number = money / x; // 可购买数量
            curprice = x; // 当前价格
        }
        if (number > 100000) // 数量超出限制
            number = 100000;
        if (x > curprice) // 高价
        {
            money += number * (x - curprice); // 利润
            curprice = x;
        }
    }
    printf("%lld\n", money);
    return 0;
}

The end.
2018-08-27 星期一