Codeforces 155B C++解析
时间: 2024-05-29 09:12:20 浏览: 9
题目描述
给定一个 n 个元素的数组 a,数组中的元素可以是正整数也可以是 0,你需要从中选出尽可能多的数,使得它们的和不超过 k。每个数最多只能选一次。
输入格式:
第一行包含两个整数 n 和 k。
第二行包含 n 个整数,表示数组 a。
输出格式:
输出一个整数,表示最多能选出的数的个数。
数据范围:
1≤n≤1000,
1≤k≤10^9,
0≤a[i]≤10^4
题目分析
这道题可以使用贪心算法来解决。具体做法是,我们将数组 a 按照值从大到小排序,然后从前往后遍历数组,每次选取一个数,如果选取这个数后总和不超过 k,就将这个数加入到答案中,否则不选取这个数。最后输出答案的大小即可。
代码实现
相关问题
codeforces 1806C解析C++
题目链接:https://codeforces.com/problemset/problem/1806/C
题意:
给定一个长度为 $n$ 的字符串 $s$ 和一个整数 $k$,每次操作可以将字符串中的一个字符改为另一个字符(不同位置可以改成不同的字符),问最少需要多少次操作才能将字符串变为 “No”(即不能再划分为至少 $k$ 个相同的子串)。
解法:
首先,我们可以将字符串 $s$ 划分成若干个相同的子串,设每个子串的长度为 $len$,则 $n=kl$,其中 $l$ 为每个子串的长度。
因此,我们可以考虑暴力枚举每个子串的长度 $l$,那么 $k$ 也可以通过 $n$ 和 $l$ 推出,即 $k=\frac{n}{l}$。
接下来,我们需要判断这个 $l$ 是否可行,即判断字符串 $s$ 是否能被划分成若干个长度为 $l$ 的子串。我们可以使用哈希来快速判断。对于每个 $l$,我们将字符串 $s$ 分成 $k$ 个子串,分别计算每个子串的哈希值,如果所有子串的哈希值都相同,则说明可以划分成若干个长度为 $l$ 的子串,否则不行。
最后,我们只需要统计所有可行的 $l$ 中最小的操作次数即可。
时间复杂度为 $O(n\log n)$。
代码实现:
C++解析codeforces 1806C
这是一道比较基础的数学题。
首先,我们可以将 $n$ 个数的和表示为 $S = a_1 + a_2 + \cdots + a_n$。
我们可以用 $k$ 表示要将这 $n$ 个数分成的部分数,那么每一部分的和为 $S/k$。
接下来我们需要证明,当 $a_1,a_2,\cdots,a_n$ 中存在一个数 $a_i$,使得它大于 $S/k$ 时,无论如何分割都不可能使得每一部分的和都小于等于 $S/k$。
我们可以假设将 $a_i$ 分到了某一部分中,那么这一部分的和就是 $S_i \geq S/k + a_i > S/k$,剩下的 $n-1$ 个数的和为 $S-S_i$。
如果我们将这 $n-1$ 个数分成 $k-1$ 部分,那么每一部分的和为 $(S-S_i)/(k-1)$。
因为 $S_i > S/k$,所以 $(S-S_i)/(k-1) < S/k$,即这 $n-1$ 个数无论如何分割都可以使得每一部分的和都小于等于 $S/k$。
所以,为了使得每一部分的和都小于等于 $S/k$,我们需要将所有大于 $S/k$ 的数都分到不同的部分中。
那么,我们可以先将原数组从大到小排序,然后依次将每一个大于 $S/k$ 的数分到不同的部分中,如果已经分到了 $k$ 个部分,则将剩下的大于 $S/k$ 的数全部舍弃。
最后,我们统计一下每一部分的和即可。时间复杂度为 $O(n\log n)$。