CF1606C Banknotes
题目大意:有 n 种钞票,面值分别为 1 0 a [ i ] 10^{a[i]} 10a[i] (0<=a[i]<=10),为升序排列且保证第一个为0,给你一个k,代表可用的钞票数,求用 k 张钞票不能表示出的最小值,共有 t 组数据。
算法思路:逻辑推理,二分,贪心。
想法:
1、首先由于数组是升序排列,且相邻两个元素之间必定有正整数差,可以进行一个贪心的思想。
2、贪心思想:可以先想一个栗子,假如有面值为1和1000的钞票,如果 k 大于1000的话,首选999张面值为1的钞票,其余的全部选1000面值的,很显然这是最优解。如果换成100和100000呢?方式相同。由此就可以得知一个通法:从小到大对于每一对相邻元素,在总数小于 k+1 的情况下加入 1 0 a [ i ] − a [ i − 1 ] 10^{a[i]-a[i-1]} 10a[i]−a[i−1]-1 张面值为 a[i-1] 的钞票,如果大于等于 k+1,剩余的钞票全选面值为 a[i-1] 的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,k,a[15],ans;
ll cf(ll x){
ll xx=1;
for(int i=1;i<=x;i++) xx*=10;
return xx;
}
int main(){
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&k);
memset(a,0,sizeof(a));
ans=0;k++;
for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}
for(int i=2;i<=n;i++){
ll tot=cf(a[i]-a[i-1])-1;
if(tot<k){
ans+=cf(a[i-1])*tot;
k-=tot;
}
else{
ans+=cf(a[i-1])*k;
k=0;
}
}
if(k>0){
ans+=k*cf(a[n]);
}
printf("%lld\n",ans);
}
return 0;
}
PS:作为一名蒟蒻,对于八方神犇的合理建议都是感激不尽的儿~~