Atcoder abc257 E

E - Addition and Multiplication 2

题意:

给你一个数字n表示你现在拥有的金额

然后给你1~9每个经营额所需要的成本, 设总经营额为x, 当前使用的经营额为y, 则每一次使用经营额时都有x=10*x+y

问, 如何在使用不大于成本数量的金额下, 使得经营额最高

例如:

5
5 4 3 8 1 6 7 6 4

成本为5

接下来为1~9的经营额

1 2 3 4 5 6 7 8 9

5 4 7 8 2 6 7 6 3

先选择9的经营额: 现在有x=0+9 此时n=5-3=2

再选择5的经营额: 现在有x=9*10+5 此时n=2-2=0

首先根据贪心的思想

我们很容易想得到, 想要尽可能得到一个大的数字, 先考虑位数更大, 再考虑高位数字更大

那么对于此题

我们先算出成本在1~9的经营额下最小的成本能使用的最多次数(也就是考虑多的位数)

次数=总成本/经营额下的最小成本

算出次数之后考虑数字能否在保持位数最大的同时在高位数字贪心

void solve()
{cin>>n;ll mmin=0x3f3f3f3f;for(int i=1;i<=9;i++){cin>>arr[i];mmin=min(mmin,arr[i]);//找出成本最小的数字}m=n/mmin;//最大位数for(int i=0;i<=m;i++)/对每一位数枚举 从高位开始枚举for(int j=9:j>=1;j--)//贪心{if(n-arr[j]>=mmin*(m-i))//保持位数最大的同时在高位数字贪心{n-=arr[j];cout<<j;break;}}return;
}