CodeForce刷题表

Day3

1606C - Banknotes

题意:

有n种面值的钱,每种面值10^a[i]。找到最小的一个不能被k张任意面额的钱恰好支付的价格。

思路：

在一种面额能被另一种面额替代之前如果数量不够，那么就是答案的数值(比如有1和100两种面额，但是k=98，那么99就是答案，因为98张面额为1的不能支付99，选择了100的更是没办法恰好支付！)

因此先把每种面额能转换的张数记录下来，看能不能填满，然后再把多余的放在最后就可以了。

不能是k张最小值+最小面额(例如:已经有9个1，+1就一定能进位，必然可以用小于k张来代替)，而是k+1张不断的填。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
ll a[15],b[15];
int main(){
 	int t;
 	cin>>t;
 	while(t--) {
 		ll n,k,cnt=0,x;
		cin>>n>>k;
		for(int i=1;i<=n;i++) {
			cin>>x;
			a[i] = pow(10,x); //求面额
			if(i==1)	continue;
			b[++cnt] = (a[i]/a[i-1])-1; //求差值
		}	
		k++; //用k+1张来求
		ll res = 0;
		cnt = 1;
		while(k>=b[cnt] && cnt<n) {
			k -= b[cnt];
			res += a[cnt] * b[cnt];
			cnt++;
		}
		res += a[cnt] * k;
		cout<<res<<endl;
	}
	
	return 0;
}

总结：

其实想一想也是用循环来做这样的题，考虑好关系就好了。

1606B - Update Files

题意：

n台电脑，k条数据线，开始有一台电脑有信息，每台电脑可以通过一条数据线把信息传给另一台，问最少需要传多少次。

思路：

首先在数据线足够的时候数量是2的？次幂台电脑上传输数据，数据线不够以后每次增加数据线条数的电脑。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
int main(){
 	int t;
 	cin>>t;
 	while(t--) {
		ll n,k;
		ll tmp = 1;
		ll res = 0;
		cin>>n>>k;
		while(tmp < k)
			tmp *= 2,res++; //数据线足够的时间需要传几次
		n -= tmp;
		if(n>0)
			res += (n-1)/k+1;//数据线不足时需要传几次
		cout<<res<<endl;
	}
	
	return 0;
}

总结：

考虑有几种状态，即数据线足够时和数据线不足时。根据每种状态来求解。