I - Arbitrage
2024-10-20 18:53:15
题目大意:套汇
套利是使用货币汇率的差异将一个单位的货币转换为多个相同的货币单位,例如1美元可以买0.5英镑,1英镑可以买10法郎,1法郎可以买0.21美元,然后聪明的人经过一些列兑换可以得到 1*0.5*10*0.21 = 1.05美元,盈利百分之5,你的工作就是判断是否能套汇成功(不得不说这个描述简介漂亮,没有一句废话)。
/////////////////////////////////////////////////////////////
这道题有点类似以前做过的汇率问题,不过没有指定哪一个是自己持有的货币,估计可以是任意一种能变多都行,试一下吧,用每一个货币都试试,反正最多30种,也不算多
方法没错,不过消耗的时间比较多,应该是map比较耗时,以后小心map
#include<algorithm>
#include<queue>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<string>
#include<map>
#include<iostream>
using namespace std; const int maxn = ;
const int oo = 0xfffffff;
const double StartMoney = ; struct node
{
int y;
double rate;
node(int y, double r):y(y), rate(r){}
};
vector<node> G[maxn];
double v[maxn]; void Initialization(int s, int N)//初始化变量
{
for(int i=; i<=N; i++)
v[i] = -oo; v[s] = StartMoney;
}
int Spfa(int s)
{
queue<int> Q;
Q.push(s); while(Q.size())
{
int i = Q.front();Q.pop();
int len = G[i].size(); for(int j=; j<len; j++)
{
node q = G[i][j];
double k = v[i] * q.rate; if(k > v[q.y])
{
v[q.y] = k;
Q.push(q.y);
}
} if(v[s] > StartMoney)
return ;
} return ;
} int main()
{
int N, M, t=; while(scanf("%d", &N), N)
{
int i;
double r;
string A, B;
map<string, int> a; for(i=; i<=N; i++)
{
cin >> A;
a[A] = i;
} scanf("%d", &M); for(i=; i<=M; i++)
{
cin >> A >> r >> B;
int x = a[A], y = a[B];
G[x].push_back(node(y, r));
} for(i=; i<=N; i++)
{
Initialization(i, N);
if(Spfa(i) == )
break;
} if(i <= N)
printf("Case %d: Yes\n", t++);
else
printf("Case %d: No\n", t++); for(i=; i<=N; i++)
G[i].clear();
} return ;
}
最新文章
- js创建对象的四种方式
- Ftp软件
- Scala 深入浅出实战经典 第58讲:Scala中Abstract Types实战详解
- #Linux学习笔记# Linux在线帮助文档man page
- POCO 是什么?
- GC之三--GC 触发Full GC执行的情况及应对策略
- leetcode:Path Sum (路径之和) 【面试算法题】
- IPC——匿名管道
- [ES6] 20. Polyfills
- css3 2D变换 transform
- bzoj千题计划108:bzoj1018: [SHOI2008]堵塞的交通traffic
- python开发:python基本数据类型
- 记python使用grpc
- ubuntu 谷歌浏览器打开时需要输入密码来解锁密码环
- Freemarker 对于数字的循环
- 单元测试系列之二:Mock工具Jmockit实战
- 大数据在教育中的应用 part2笔记
- php 类与对象
- 使用Kotlin&;Anko, 扔掉XML开发Android应用
- Chrome 开发工具之Timeline/Performance