0316MY
# 在线购物
假设你面临一个在线购物选择,有n件商品可供挑选,其中部分商品参与折扣活动(95折)。你有一个预算限制k,现在要决定在不超过预算的前提下,最多可以购买多少件参与折扣的商品。
# 输入描述
输入包含三行。
第一行两个正整数
# 输出描述
一行一个整数表示答案。
# 样例输入
6 13
4 7 5 3 6 8
0 1 0 1 1 1
2
3
# 样例输出
3
# 样例解释
可以选择第1,3,4件物品,最多装3件。
# 思路分析
贪心问题
为什么不是动态规划?因为只要求件数最大,而没有要求背包所装体积最大,或是背包所装物品权值最大。
在这个问题中,就是没有要求钱尽量花光,或者买到的物品价值最大。
只是要求件数最大,从最便宜的东西开始买,肯定买到的件数最多。
# 代码实现
# CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
double price[N];
int main(void) {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> price[i];
}
string s;
cin >> s;
for (int i = 1; i <= n; i++) {
if (s[i - 1] == '1') price[i] *= 0.95;
}
sort(price + 1, price + 1 + n);
int ans = 0;
double sum = 0;
for (int i = 1; i <= n; i++) {
sum += price[i];
if (sum <= k) ans++;
else break;
}
cout << ans;
return 0;
}
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
32
33
34
# Java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
double[] price = new double[n + 1];
for (int i = 1; i <= n; i++) {
price[i] = scanner.nextDouble();
}
String s = scanner.next();
for (int i = 1; i <= n; i++) {
if (s.charAt(i - 1) == '1') {
price[i] *= 0.95;
}
}
Arrays.sort(price, 1, n + 1);
int ans = 0;
double sum = 0;
for (int i = 1; i <= n; i++) {
sum += price[i];
if (sum <= k) {
ans++;
} else {
break;
}
}
System.out.println(ans);
}
}
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
32
33
34
35
36
# Python
n, k = map(int, input().split())
price = list(map(float, input().split()))
s = input()
for i in range(n):
if s[i] == '1':
price[i] *= 0.95
price.sort()
ans = 0
total = 0
for i in range(n):
total += price[i]
if total <= k:
ans += 1
else:
break
print(ans)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 狼哥的字符串切割挑战
狼哥有一个独特的游戏:给定一个字符串,他想将其分割成两个非空部分,这两部分的权值必须相等。这里的权值是指字符串中辅音和元音字母数量差的绝对值。比如说,对于字符串"arcaea",其权值为
# 输入描述
一个只包含小写字母的字符串,其长度不会超过
# 输出描述
满足条件的分割方案总数。
# 样例输入
arcaea
# 样例输出
2
# 数组最大公因子为素数的可能性
狼哥有一个数组,其长度为
# 输入描述
首先输入一个正整数
# 输出描述
如果狼哥能够通过操作使数组中所有元素的最大公因子变为素数,则输出 "YES",否则输出 "NO"。如果答案为 "YES",则在下一行按升序输出所有可能的最大公因数。
# 样例1输入
4
1 3 5 9
2
# 样例1输出
YES
3
2
# 样例2输入
4
2 2 2 2
2
# 样例2输出
YES
2
2
# 狼哥的排列挑战
狼哥手中有一串数字,他可以无限次地将任一数字增加1。狼哥想探索,通过这种方式,他最多能创造出多少个独特的序列?一个序列被认为是独特的,如果它的长度等于数字串的长度,并且从1到该长度的每个数字都恰好出现一次。
# 输入描述
首先输入一个正整数
# 输出描述
输出一个整数,表示能够生成的独特序列的最大数量,结果需要对
# 样例输入
3
1 2 1
2
# 样例输出
4