链接:https://ac.nowcoder.com/acm/contest/59284/D 来源:牛客网 题目描述 牛牛面前有一个由 � n 个整数组成的数组 � 1 , � 2 , . . . , � � A 1 ,A 2 ,...,A n 。 牛牛打算对这个数组进行若干次操作。 每次操作牛牛可以选择 � 1 , � 2 , . . . , � � A 1 ,A 2 ,...,A n 中的任意一个非负整数,记所选数的下标为 � k。然后牛牛会把 � � , � � + 1 , . . . , � � A k ,A k+1 ,...,A n 都减少 � � A k 。 牛牛想知道他对这个数组进行恰好 � m 次操作后,数组中所有数的和最少是多少。
时间: 2024-01-18 15:02:06 浏览: 203
这是一道典型的贪心算法题目,可以利用贪心思想来解决。
具体做法如下:
1. 计算数组的前缀和,即 preSum[i] 表示前 i 个数的和。
2. 将数组按照从小到大的顺序排序。
3. 从小到大枚举每个数,假设当前枚举到第 i 个数,那么将前 i-1 个数都减去 nums[i],再将数组中元素从 i+1 到 n 都减去 nums[i]。这样操作后,数组中第 i 个数的值为 0,前 i-1 个数的和变成了 preSum[i-1]-i*nums[i],而后面的数的和仍然为preSum[n]-preSum[i]-(n-i)*nums[i]。
4. 计算操作 m 次后数组的总和,即为 preSum[n]-m*min(nums[i])。
时间复杂度为 O(nlogn),空间复杂度为 O(n)。
相关问题
链接:https://ac.nowcoder.com/acm/contest/92236/J 来源:牛客网 小红拿到了一个仅由大小写字母组成的长度为 𝑛 n的字符串,她希望把前 𝑘 k个字母变成大写,后 𝑛 − 𝑘 n−k个字母变成小写
这是一个简单的字符串操作题目,要求将给定字符串中的前k个字符转换为大写,其余的转换为小写。在C语言中,我们可以使用`toupper()`和`tolower()`这两个标准库函数来进行字符的大小写转换。
```c
#include <stdio.h>
#include <ctype.h>
void convert_case(char *str, int k) {
for (int i = 0; i < k; i++) { // 将前k个字符转为大写
str[i] = toupper(str[i]);
}
for (int i = k; i < strlen(str); i++) { // 将剩余字符转为小写
str[i] = tolower(str[i]);
}
}
int main() {
char input[100]; // 假设字符串最大长度不超过100
int n, k;
printf("请输入字符串(忽略空格)和需要转换的大写字母数量: ");
fgets(input, sizeof(input), stdin); // 注意处理换行符
input[strlen(input) - 1] = '\0'; // 去掉末尾的换行符
sscanf(input, "%d %d", &n, &k);
if (k <= n && k >= 0) {
convert_case(input, k);
printf("转换后的字符串是: %s\n", input);
} else {
printf("k的值不正确,请确保0 <= k <= n。\n");
}
return 0;
}
```
在这个程序中,首先从用户那里获取字符串和k的值,然后调用`convert_case`函数执行转换。如果k的值在有效范围内(大于等于0且小于或等于n),则输出结果;否则提示错误。
链接:https://ac.nowcoder.com/acm/contest/68233/B 来源:牛客网 输入三个整数,求以下三数的和, 1+2+...+a + 12+22+...+b2 + 1/1+1/2+...+1/c
这道题目需要求解的是一个数学问题,需要对题目进行分析。首先,我们可以将题目中的三个数列分别求和,得到1到a的和、12到b的平方和以及1到1/c的倒数和。接下来,我们需要根据引用[3]中的思路,从中任取两场比赛,对满足和各出现一次的做统计,结果数即为(a-1)*(b-1)*(c-1)。最终答案就是三个数列的和乘以结果数。具体的计算过程可以参考下面的公式:
sum = (a*(a+1))/2 + (b*(b+1)*(2*b+1))/6 + (1/((double)c)*(1+(1/((double)c-1)))) * (a-1)*(b-1)*(c-1);
其中,(a*(a+1))/2表示1到a的和,(b*(b+1)*(2*b+1))/6表示12到b的平方和,(1/((double)c)*(1+(1/((double)c-1))))表示1到1/c的倒数和,(a-1)*(b-1)*(c-1)表示结果数。
阅读全文