"华为OD真机算法题：货币兑换最大最小化"

需积分: 47 113 浏览量更新于2024-01-05 50 收藏 1.41MB PDF 举报

本题目要求实现货币之间的兑换功能，根据给定的汇率进行最大兑换和最小兑换。根据题目给出的默认汇率，我们可以按照如下步骤来实现。首先，我们需要将输入转化为相应的数字，表示货币之间的汇率。根据输入示例，可以得到以下对应关系： 1 CNY = 2 HKD 1 USD = 8 CNY 1 GBP = 2 USD 然后，我们根据题目要求来实现最大兑换和最小兑换的功能。最大兑换的策略是尽量往价值高的货币兑换。因此，我们需要找到价值最高的货币，然后将剩余的金额用下一位价值次高的货币进行兑换，直至兑换完成。在计算最大兑换时，我们需要根据汇率计算出每种货币所能兑换的最大数量。具体的计算方法如下： 1. 根据输入的数字，计算出1CNY兑换成多少HKD。例如，输入示例中给出的是127 HKD，则1CNY = 127 HKD。 2. 根据1 CNY = 2 HKD的汇率，计算出可以兑换的最大数量。例如，127 HKD可以兑换的最大数量为127/2 = 63。 3. 根据题目要求，将兑换的结果从高到低排列。例如，兑换结果为Currency(127, HKD) = 3 GBP 1 USD 7 CNY 1 HKD。最小兑换的策略是尽量往价值低的货币兑换，直接转换为多少HKD即可。因此，我们只需要根据输入的数字，计算出它对应的HKD数量即可。在计算最小兑换时，我们需要根据汇率计算出对应货币的数量。具体的计算方法如下： 1. 根据输入的数字，计算出1CNY兑换成多少HKD。例如，输入示例中给出的是127 HKD，则1CNY = 127 HKD。 2. 最小兑换结果为Currency(20, CNY) = 40 HKD，直接将兑换的结果表示为对应的HKD数量即可。需要注意的是，汇率是实时变化的，但在短期内大致符合当前价值规律。因此，每组输入数据都会有不同的输入汇率，需要按照给定的汇率进行兑换。综上所述，根据题目要求，我们实现了货币最大兑换和最小兑换的功能。根据输入的汇率和金额，我们可以按照相应的规则进行兑换，得到最终的结果。

order.count=1;

staticsMap.insert(make_pair(s,order));

}

//统计所有第一个下单的人数

size_t freeOrderNum=0;

map<string,FirstOrder>::iterator it=staticsMap.begin();

while(it!=staticsMap.end())

{

freeOrderNum+=it->second.count;

it++;

}

cout<<freeOrderNum<<endl;

}

11、【股票最大收益】

题目：假设知道某段连续时间内股票价格，计算通过买入卖出可获得的最大收益。

输入一个大小为 n 的数 price(p1,p2,p3,p4…….pn),pi 是第天的股票价格。

pi 的格式为股票价格(非负整型)加上货币单位 Y 或者 S,其中 Y 代表人民币,S 代表美元,这里规定 1 美元可以兑换 7 人民币。

Pi 样例 1：123Y 代表 123 元人民币

pi 样例 2：123S 代表 123 元美元,可兑换 861 人民币

假设你可以在任何一天买入或者卖出胶票,也可以选择放弃交易,请计其在交易周期 n 天内你能获得的最大收(以人民币计算。

输入描述:

输入一个包含交易周期内各天股票价格的字符串，以空格分隔。不考虑输入异常情况。

输出描述：

输出一个整型数代表在交易周期 n 天内你能获得的最大收益，n 不能超过 10000

备注：股票价格只会用 Y 人民币或 S 美元进行输入，不考虑其他情况。

示例 1

输入：

2Y 3S 4S 6Y 8S

输出：

#include <iostream>

#include <string>

#include <vector>

using namespace std;

int MaxProfit(vector<int> prices);

int Split(string input, vector<string>& output, string pattern);

int main(int ragc, char** argv)

{

string inputstring;

while (1)

{

getline(cin, inputstring);

if (!inputstring.empty())

{

vector<string> prices_string;

Split(inputstring, prices_string, " ");

vector<int> prices_int;

for (int i = 0; i < prices_string.size(); i++)

{

if (prices_string[i][prices_string[i].size() - 1] == 'Y')

{

prices_int.push_back(atoi((prices_string[i].substr(0, prices_string[i].size() - 1)).c_str()));

}

else

{

prices_int.push_back(7 * atoi((prices_string[i].substr(0, prices_string[i].size() - 1)).c_str()));

}

cout << MaxProfit(prices_int) << endl;

}

return 0;

}

int MaxProfit(vector<int> prices)

{

int len = prices.size();

vector<int> change(len, 0);

int maxProfit = 0;

for (int i = 1; i < len; i++)

{

change[i] = prices[i] - prices[i - 1];

if (change[i] > 0)

{

maxProfit += change[i];

}

return maxProfit;

}

int Split(string input, vector<string>& output, string pattern)

{

string::size_type pos;

input += pattern; //扩展字符串以方便操作

for (int i = 0; i < input.size(); i++)

{

pos = input.find(pattern, i);

if (pos < input.size())

{

string s = input.substr(i, pos - i);

if ((s != " ") && (!s.empty()))

{

output.push_back(s);

}

i = pos + pattern.size() - 1;

}

return 0;

}

12、【独木桥】

题目描述

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我

们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中 L 是桥的长度）。坐标为 0 的点表示桥的起点，坐标为 L 的点表示桥的终点。青蛙从桥的起

点开始，不停的向终点方向跳跃。一次跳跃的距离是 S 到 T 之间的任意正整数（包括 S ,T）。当青蛙跳到或跳过坐标为 L 的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度 L，青蛙跳跃的距离范围 S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数

输入输出格式

输入格式：

输入文件 river.in 的第一行有一个正整数 L（1<=L<=10^9），表示独木桥的长度。第二行有三个正整数 S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的

个数，其中 1<=S<=T<=10，1<=M<=100。第三行有 M 个不同的正整数分别表示这 M 个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一

个空格隔开。

输出格式：

输出文件 ri v e r. ou t 只包括一个整数，表示青蛙过河最少需要踩到的石子数。

示例 1

输入：

2 3 5

2 3 5 6 7

输出：

说明

对于 30%的数据，L<=10000；

对于全部的数据，L<=109。

解题思路

和前几天写的吃药问题差不多，l 的范围太大，无法作为数组下标，所以先离散化，再 DP。两点间的距离 d 大于 t 时，一定可以由 d%t 跳过来，所以最多只需要 t+d%t 种

距离的状态就可以表示这两个石子之间的任意距离关系。这样就把题目中的 10^9 压缩成了 2*t*m 最多不超过 2000，然后就可以放心大胆地用 DP 了。不过要注意题目中的

“当青蛙跳到或跳过坐标为 L 的点时，就算青蛙已经跳出了独木桥”，所以 DP 的终点是一个范围而非确切的一个点，最后还要在这个范围内取最小值。

#include <iostream>

#include <string.h>

#include <algorithm>

using namespace std;

int dp[1000010];

int main(int argc,char** argv)

{

int i,l,n,s,t,d,j,m;

while(1)

{

cin>>l>>s>>t>>n;

memset(dp,0,sizeof(dp));

for(i=0;i<n;i++)

{

cin>>d;

dp[d]=1;

}

for(i=l;i>=0;i--)

{

m=110;

for(j=s;j<=t;j++)

{

m=min(dp[i+j],m);

}

dp[i]+=m;

}

cout<<dp[0]<<endl;

}

return 0;

}

剩余144页未读，继续阅读

小菜鸟_程序员

粉丝: 2
资源: 5

"华为OD真机算法题：货币兑换最大最小化"

华为OD、大厂笔试算法题

华为研发类笔试编程题

华为机试题（自己整理附有个人的代码）

华为od机考算法题题库，机考算法题，含答案和解题思路，学习算法和刷题可以用

华为od机试算法题库及答案

华为OD刷刷华为OD的算法题

华为od算法题 华为OD算法 1、什么是OD算法？ OD算法（Optimized Disparity Algorithm），又称

华为od性格测试题及答案

华为OD机考100题（含答案）.docx

python 华为 od 机试题试题答案.zip

最新资源

华为od算法题华为OD算法 1、什么是OD算法？ OD算法（Optimized Disparity Algorithm），又称