CF1606C Banknotes

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:作为一名蒟蒻,对于八方神犇的合理建议都是感激不尽的儿~~

上一篇:P3195 [HNOI2008]玩具装箱


下一篇:Codeforces Round #691 (Div. 2)