小八打了 n 次攻击,第 i 次攻击可以造成 ai 点伤害。现在你可以选择其中的 m 次攻击使得其伤害翻倍。请你回答最多可以造成多少总伤害。 输入格式 第一行 2 个整数 n,m ,表示攻击次数和可以选择伤害翻倍的攻击次数。 接下来一行包含 n 个整数 a1,a2,...,an 。 输出格式 仅 1 行 1 一个正整数,表示最多能造成的总伤害。 样例输入 5 3 3 9 5 3 2 样例输出 39 数据规模 对于 100% 的数据,保证 1≤m≤n≤103,1≤ai≤109 。c++实现代码
时间: 2023-02-09 12:08:48 浏览: 53
这是一道贪心题。题目中给出了n次攻击和m次可以选择伤害翻倍的攻击。要求输出最大总伤害。
思路:先将n次攻击按照伤害从大到小排序,然后选择前m次伤害最大的攻击进行翻倍。最后计算总伤害。
C++ 代码如下:
```
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,a[1005],ans;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
reverse(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
if(i<=m) ans+=a[i]*2;
else ans+=a[i];
}
cout<<ans;
return 0;
}
```
相关问题
小八打了 n 次攻击,第 i 次攻击可以造成 ai 点伤害。现在你可以选择其中的 m 次攻击使得其伤害翻倍。请你回答最多可以造成多少总伤害。c++实现
### 回答1:
小八打了 n 次攻击,第 i 次攻击可以造成 ai 点伤害。现在你可以选择其中的 m 次攻击使得其伤害翻倍。最多可以造成的总伤害可以用贪心算法来解决。
在 c 语言中可以这样实现:
```
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return *(int *)b - *(int *)a;
}
int main() {
int n, m, i, damage = 0;
scanf("%d %d", &n, &m);
int a[n];
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
qsort(a, n, sizeof(int), cmp);
for (i = 0; i < n; i++) {
damage += a[i];
if (i < m) {
damage += a[i];
}
}
printf("%d\n", damage);
return 0;
}
```
这段代码先把 n 次攻击的伤害数组按照从大到小排序,然后从前往后遍历伤害数组,对前 m 次攻击的伤害进行翻倍。最后输出总伤害。
### 回答2:
首先,我们需要找出造成伤害最高的 m 次攻击。
假设小八共打了 n 次攻击,每次攻击造成 ai 点伤害。我们可以使用动态规划来解决这个问题。
令 dp[i][j] 表示在前 i 次攻击中选择 j 次攻击使其伤害翻倍所能造成的最大总伤害。
状态转移方程为:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + ai)
其中,dp[i-1][j-1] + ai 表示选择第 i 次攻击使其伤害翻倍,dp[i-1][j] 表示不选择第 i 次攻击使其伤害翻倍。
最终的答案为 dp[n][m]。
下面是源代码的实现:
def maxDamage(n, m, a):
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, min(i, m) + 1):
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + a[i-1])
return dp[n][m]
其中,参数 n 表示小八打了 n 次攻击,参数 m 表示可以选择其中的 m 次攻击使其伤害翻倍,参数 a 表示每次攻击造成的伤害。
这样,你可以调用函数 maxDamage(n, m, a) 来求解最多可以造成的总伤害。
### 回答3:
首先,我们可以使用一个数组sum来存储每次攻击的累积伤害,其中sum[i]表示前i次攻击的总伤害。
然后,我们可以使用动态规划的方法来计算最多可以造成的总伤害。定义一个大小为m的二维数组dp,其中dp[i][j]表示前i次攻击中选择j次攻击翻倍后的总伤害。
初始化时,dp[0][0]为0,表示前0次攻击中没有选择攻击翻倍。
接下来,我们可以使用以下状态转移方程来计算dp数组的值:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + 2*sum[i])
其中dp[i-1][j]表示当前第i次攻击不进行翻倍,dp[i-1][j-1] + 2*sum[i]表示当前第i次攻击进行翻倍,伤害为两倍的累积伤害。
最后,我们需要遍历dp[m]数组中的所有元素,找到最大值,即为最多可以造成的总伤害。
以下是使用Python语言实现上述算法的代码:
```python
def max_damage(n, a, m):
sum = [0] * (n + 1)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
sum[i] = sum[i - 1] + a[i]
for i in range(1, n + 1):
for j in range(1, min(i, m) + 1):
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + 2 * sum[i])
return dp[n][m]
# 测试用例
n = 5
a = [0, 1, 2, 3, 4, 5]
m = 2
print(max_damage(n, a, m)) # 输出9
```
根据给定的攻击次数n、每次攻击的伤害值a和要翻倍的攻击次数m,该算法可以计算出最多可以造成的总伤害。对于给定的测试用例,最多可以造成的总伤害为9。
小八喜欢吃苹果。他现在有m(m≤100)个苹果,吃完一个苹果需要花费t(t≤100)min,吃完一个后立刻开始吃下一个。现在时间过去了 s(s≤m·t)min。请编写程序输出小八现在还有几个完整的苹果?
根据题意,小八吃一个苹果需要花费t分钟,所以在s分钟内可以吃s/t个苹果。那么小八现在还剩下的完整苹果数量就是原本的m个苹果数量减去吃掉的苹果数量,即:
m - (s/t)
代码实现如下:
```
#include <iostream>
using namespace std;
int main() {
int m, t, s;
cin >> m >> t >> s;
int eaten = s / t; // 吃掉的苹果数量
int left = m - eaten; // 剩下的完整苹果数量
if(left < 0) left = 0; // 若剩下的数量小于0,则输出0
cout << left << endl;
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)