与班尼特·胡迪一起做生意 AC
Time Limit: 1 s Memory Limit: 256 MB
Description
马爷作为2-80X的资深土财主,靠着敏锐的商业嗅觉不断买卖商品赚的盆满钵满。近日来大家发现了异样。马爷做生意从来只有赚钱,永远不会亏本。
坦诚的马爷公开了这个秘密。马爷早些年通过不可描述的手段弄到了一个可以预测价格的机器。通过它,马爷可以知道某个商品在今后n天的价格。但是作为牺牲,马爷在这n天之内最多只能分别进行一次该商品的买进和卖出。
现在大家都知道了这个秘密。但是你真的可以选对时间买进卖出,使得自己的收益最大化吗?
Input
第一行为数字T,代表接下来有T组数据(T<=10)
每组数据第一行为数字N,代表知道N天的价格信息(N<=10^6)
每组数据第二行为N个正整数ai,ai代表第i天的价格(0<ai<10^9,1<=i<=N)。
Output
每组数据输出占一行,一行仅输出一个数字X,代表最多可以赚X元
(注意:买进一定在卖出之前)
Samples
input:
3
5
1 2 3 4 5
5
1 2 3 1 5
5
5 4 3 2 1
output:
4
4
0
Hint
样例一中在第1天买进第5天卖出可以赚4元
样例二中在第1天买进和第4天买进第5天卖出都可以赚4元,
样例三中在每天都在跌,怎么买都是亏钱,所以选择不买不卖
Author
Source
题解:题目很简单,找到买进价格最低和卖出最高之差,没有输出0;
思路:一开始的结构体排序比较的思路,然后超时。。被大佬们说傻。代码比较简单,一边读入,找到前n-1天最便宜的价格,与第n天价格最差,max取差值最大的。
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
int T,n,money,ans,Min;
scanf("%d",&T);
while(T--)
{
ans=; //每一次都要清空数据啊,不然会被保留
scanf("%d",&n);
scanf("%d",&Min); //先把第一次输入当作最小值
for(int i=;i<=n;i++)
{
scanf("%d",&money);
Min=min(Min,money); //与后进来的数据比较取最小
ans=max(money-Min,ans); //剪一下取较大值
}
printf("%d\n",ans);
}
return ;
}