2014
03-01

# Stock

Recently, the Chinese stock market begins to heat up slowly. It is said that in 2009 China’s Stock market will re-enter the bull market. Let’s pay some attention to the stock.

Stock is defined as a purely economic issue, it is actually representative of your company’s ownership of the shares. But in fact most investors regard it as a kind of commodities, not the production which are made in the factories. Since it is a commodity, there is measurement problem. Fruits are bought by jin, TV sets are bought by set. While the stock is bought in share. Stock and TV set here in set is similar. That is, we can not buy half-shares, and at least buy one share. Of course, stock and fruit, TV set, are different. Stock is so different as the price is changing at all time. Everyone can buy it legally in the trading market. Stock trading costs transaction fees. And the calculation is quite complicated so we don’t dive into this.

To make it easier, we have the problem simplified. First of all, ignore the price changing within a day, meaning that only one constant price on a certain day. Then assuming that only to pay fees when stock are sold, the transaction fee is a fixed value of s.

For example, if the transaction fee is $100. The stock price on the first day is$10 per share. We have $10,000, so we can buy 1,000 shares. The next day, the stock price rise to$11 per share. We sell all the 1,000 shares, so get $11,000. It cost$100 for the fee. So the profit is \$900.

In this problem the transaction times is unlimited. You can sell and buy stock time and time again if you like. Now, if we know the stock prices in n trading days, the fee and the initial funding. So, how much money can we earn at most in the n days?

There are multiple cases.

The first line contains the number of test cases t.

For each case, the first line contains three integers n (1<n<=3000), s (0<=s<=10000), p (0<p<=100000), respectively, the number of trading days, fee and initial funding. The second line contains n positive real numbers which are greater than 0 (up to two significant figures after the decimal point), the prices are given in chronological order of the n trading days.

There are multiple cases.

The first line contains the number of test cases t.

For each case, the first line contains three integers n (1<n<=3000), s (0<=s<=10000), p (0<p<=100000), respectively, the number of trading days, fee and initial funding. The second line contains n positive real numbers which are greater than 0 (up to two significant figures after the decimal point), the prices are given in chronological order of the n trading days.

3
4 10 100
10.00 1.00 12.00 10.00
3 10 100
10.5 5.3 1.9
5 10 100
4 1 8 2 5 

1090.00
0.00
1865.00 

#include <cstdio>
#include <queue>
using namespace std;
const int maxint=-1u>>1;
const int maxn=100000+10;
int n;
long long x[maxn],p[maxn],m[maxn];
typedef pair<long long,long long>pii;
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for(int i=0; i<n; ++i)
scanf("%I64d%I64d%I64d",&x[i],&p[i],&m[i]);
long long ans=0;
priority_queue<pii>que;
for(int i=n-1; i>=0; --i)
{
int s=x[i];
que.push(make_pair(p[i], m[i]));
while(s&&!que.empty())
{
pii top=que.top();
que.pop();
if(s>=top.second)
{
ans+=top.second*top.first;
s-=top.second;
}
else
{
ans+=s*top.first;
top.second-=s;
s=0;
que.push(top);
}
}
}
printf("%I64d\n",ans);
}
return 0;
}

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.