18新生赛 4. Deal
2024-09-03 20:36:36
题目描述:双十一过后,syx发现自己快要吃土了。但是机智的他决定理财。他预测了将来n天的比特币行情,发现有涨有跌,有跌有涨。手里的钱只要在比特币的浪潮中经历沉浮,低价收入,高价卖出,就可以轻易割到别人的韭菜从而致富。为了降低风险,他决定无论何时,最多手里只保留不超过1个比特币,同时他想在获利最多的情况下尽可能减少交易发生的数量。现给出n天的比特币行情,即每天的1个比特币的价值。请你求出n天后,syx最多能获利多少?在最大获利情况下的最小交易次数是多少次?我们假设初始时syx有无限的钱财,因为哪怕借钱他也要赚一波。
输入:第一行有一个整数 T, 表示共有T组数据。 0 < T<=5 每组数据两行:
对于每组数据的第一行,有一个整数 n,表示预测了 n 天的行情 (1 <= n <= 100000)
对于每组数据的第二行,有 n 个整数 ai,分别表示第 i 天的行情。(0 <= ai <= 1010)
输出
对于每一组样例,输出一行两个整数用空格隔开,表示最大获利和最小交易次数
样例输入
2
5
9 10 7 6 8
3
3 2 1
样例输出
3 4
0 0 代码
#include<stdio.h>
int main() {
int T;
long long b[6],c[6];
scanf("%d",&T);
for(int j=0; j<T; j++) {
int n,i=0,x=0,s=0,money=0;
long long a[100005];
scanf("%d",&n); //n组数据
for(i=1; i<=n; i++) {
scanf("%d",&a[i]); //n天的行情
}
for(i=1; i<n; i++) {
if(a[i+1]>a[i]) {
money=money+(a[i+1]-a[i]);
s++; //算差价,
} else {
s=0; //引入变量s作为判断标准,无论连续交易多少次,为了算最少次数,则最终次数都是2
} // 当后者比前者小,即出现亏本,s清零
if(s==1) x=x+2;
}
b[j]=money;
c[j]=x;
}
for(int i=0; i<T; i++) {
printf("%d %d\n",b[i],c[i]);
}
return 0;
} 最开始没想到引入变量s,然后就无法准确算最小交易次数。最大利益,即先找最低点,再找相邻的最高点,然后作差,然后再重复以上内容,但这样不会算最小次数。
引入变量s后,只需判断后者是否比前者大,如果大,就作差算利益,s++,s初始为0,++后为1,只要为1,则次数加2,如果出现后者比前者小,那么连续交易中断,此时s清零,为了下次的连续交易做准备。
最新文章
- 微软MVP攻略 (如何成为MVP?一个SQL Server MVP的经验之谈)
- ORACLE 物理读 逻辑读 一致性读 当前模式读总结浅析
- Asp.net中导出Excel文档(Gridview)
- 快速入门系列--WCF--05事务
- 非常完善的Log4net详细说明
- 802.11 wireless 五
- 加密app.config
- 【DP/单调栈】关于单调栈的一些题目(codevs 1159,codevs 2673)
- Android Service 通过 BroadcastReceiver 更新Activity UI
- ActiveMQ持久化方式(转)
- Android OpenGL ES 入门系列(一) --- 了解OpenGL ES的前世今生
- Linux显示系统日期
- Civil 3D 二次开发 事务
- python作用域问题
- oracle中计算两个日期的相差天数、月数、年数、小时数、分钟数、秒数等
- 004 作业二(单击弹跳li节点的每个文本节点的值;点击每个 li 节点, 若 li 节点的文本值没有 ^^ 开头, 加上,有,则去除)
- VMware Infrastructure 3 in a Cisco Network Environment
- spring eureka required a bean of type &#39;com.netflix.discovery.DiscoveryClient&#39; that could not be found.
- HDU 4348 To the moon 主席树 在线更新
- 高性能无锁队列 Disruptor 初体验