JZOJ 3241. Money

题目

Description

你在一个跨国公司负责发工资，每个工人的工资以自己本国货币结算。如果你手头上有足够的该国货币，你就直接发给他；如果没有足够的该国货币，他也不介意收到其他种类的货币，前提是按兑换关系他没有少拿就可以了。例如，有六种货币：A,B,C,D,E,F，你知道这些货币的兑换关系是：

23 A = 17 B

16 C = 29 E

5 B = 14 E

1 D = 7 F

假如有个工人过来领100 A，而你手头正好没这么多A货币，你可以考虑替换成74 B（相当于100.12 A）、115 C（相当于100.72 A）或207 E（相当于100.02 A）。你应该支付207 E，因为这最接近这个工人应得的工资。

注意根据以上的兑换关系，你无法推断货币A与D、A与F的兑换关系。

由于钱仓空间有限，每种货币你最多只能持有100000，因此你无法用E货币支付64000 A，但用73078 C来支付是允许的。

假设工人领工资时，你正好没有结算的货币了，但其他货币的钱仓都是满的。你需要写一个程序帮你计算该怎样支付这个工人的工资。

Input

输入的第一行是一个整数n，接下来的n行，每行有两种不同货币的兑换关系，形如：

val1 name1 = val2 name2

name1和name2分别是货币名，val 1和val 2是<=30的正整数，货币种类不超过8个，货币名由不超过10个字母组成。

兑换关系不存在类似1 A = 2B，1B = 2C，1C = 2A这种矛盾的情况。

紧接着有一行形如val name，代表工资额和结算的货币（val不超过100000）。

Output

输出形式为val name，val和name之间用一个空格分隔，分别代表支付的工资额及相应的货币。每个测试数据保证有唯一解。

Sample Input

输入1：

4

23 A = 17 B

16 C = 29 E

5 B = 14 E

1 D = 7 F

100 A



输入2：

1

1 USD = 2 RMB

40 RMB

Sample Output

输出1：

207 E



输出2：

20 USD

Data Constraint

货币种类不超过8个

分析

刚开始看，不就是道模拟题
打着打着发现精度好像炸了
算了不搞了
原来我理解错题了
没有四舍五入，全都要进
打了个图，flored？

代码

 1 #include<iostream>
 2 #include<map>
 3 #include<vector>
 4 #include<cstring>
 5 #define a mapp[s1]
 6 #define b mapp[s2]
 7 using namespace std;
 8 double z[10][10],kk[10];
 9 string s[10]; 
10 map<string,int> mapp;
11 int cnt,ans,n;
12 double k[10];
13 int flag[10][10];
14 double minn(double aa,double bb) {if (aa>bb) return bb; else return aa;}
15 int main ()
16 {
17     char c;
18     string s1,s2;
19     cin>>n;
20     double x,y;
21     for (int i=1;i<=n;i++)
22     {
23         cin>>x>>s1; if (!a) {a=++cnt; s[a]=s1;}
24         cin>>c;
25         cin>>y>>s2; if (!b) {b=++cnt; s[b]=s2;} 
26         z[a][b]=y/x;
27         z[b][a]=x/y;
28     }
29     for (int k=1;k<=cnt;k++)
30         for (int i=1;i<=cnt;i++)
31             for (int j=1;j<=cnt;j++)
32                 if (z[i][j]==0&&z[i][k]!=0&&z[k][j]!=0)
33                   z[i][j]=z[i][k]*z[k][j];
34     int m,l;
35     cin>>m>>s1;
36     l=a;
37     int t1,g1,wz;
38     double t2=1e9;
39     double g2;
40     for (int i=1;i<=cnt;i++)
41     {
42         if (i==l||!z[l][i]) continue;
43         g2=m*z[l][i];
44         g1=(int)(g2);
45         if (g2-g1>1e-9) ++g1;
46         if (g1>1e5) continue;
47         g2=g1*z[i][l]-m;
48         if (g2<t2)
49         {
50             t1=g1;
51             t2=g2;
52             wz=i;
53         }
54     }
55     cout<<t1<<" "<<s[wz]; 
56 }

为何要逼自己长大，去闯不该闯的荒唐