思路

首先将题目转化为塔子完成整个关卡最少损失多少生命值，这时每个回合用不用塔子起飞所造成的贡献相对独立。

考虑第 $i$ 个回合用塔子起飞，会少损失 $v_i$ 点体力，并在之后的 $n-i$ 个关卡中每关增加 $1$ 点恢复，但是会少增加$cnt_i$点体力。 这里的 $cnt_i$ 代表之前用过的塔子起飞次数。

所以选择第$i$回合所带来的增益就是 $v_i+n-i-cnt_{i-1}$ 。由于每个位置的选择是独立的(也就是说你选第1个和你选第2个是没关系的。没规定你选了第1个必须选第2个。也没规定你选了第1个就不能选第2个)。所以我们就是要求:

$$\Large max\ \sum_{i \in \{i_1,i_2,...,i_x\}}^{} v_i+n-i-cnt_{i-1} \\ \Large = \sum_{i \in \{i_1,i_2,...,i_x\}}^{} v_i-i + \sum_{i \in \{i_1,i_2,...,i_x\}}^{} n -cnt_{i-1} $$

假设我们这$x$个回合分别选的下标集合是$\{i_1,i_2,...,i_x\}$

这里的贡献被我们分成了两个部分。那么可以发现后面那一项跟下标集合没有关系，是一个常数项。它的值永远是$0+1+2+..+x-1$

举个例子:

比如总共有3个回合，我们从里面选2个回合，那么你可以试试，不管是选1,2 还是 2 , 3 还是 1 ，3 ， 它的第二项永远是$0+1$ 。

所以说后面那一项可以不看，直接就是

$$\Large = max\ \sum_{i \in \{i_1,i_2,...,i_x\}}^{} v_i-i $$

所以我们的做法就是直接对$v_i - i$ 排序,取前$x$ 大的位置的$v_i+n-i-cnt_{i-1}$ 相加即可!

代码

python

n, k = map(int,input().split())
a = list(map(int, input().split()))
b = []	#用于排序的数组
for i in range(len(a)):
	#按照上面的推导，回合数从1开始，第二维应该存i+1，但是不影响排序所以存i即可
	b.append([a[i], i])
b.sort(key = lambda x:(x[0]-x[1]), reverse = True)		#重写排序函数，按照 第一维-第二维 排序，即 v[i]-i
for i in range(k):	#在原数组中将排序后的数组的前x个置为-1，代表在这回合使用塔子起飞
	a[b[i][1]] = -1

ans = 0
cnt = 0	#cnt代表之前用过的塔子起飞次数，ans代表最后受到伤害的总和
for i in a:
	if i == -1:
		cnt += 1		#如果使用塔子起飞，则没有伤害，更新cnt
	else :
		ans += i-cnt	#不使用塔子起飞则恢复cnt点体力，
print(max(ans, 1))

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int a[100005];
vector<vector<int> >b;
bool cmp(vector<int> x,vector<int> y){	//重写排序函数，按照 第一维-第二维 排序，即 v[i]-i
    return (x[0]-x[1])>(y[0]-y[1]);
}
int main()
{
    int n,k;
    cin>>n>>k;
    for (int i=0;i<n;i++)
        cin>>a[i];
    for (int i=0;i<n;i++)
    {
        vector<int>tmp{a[i],i};	//按照上面的推导，回合数从1开始，第二维应该存i+1，但是不影响排序所以存i即可
        b.push_back(tmp);
    }
    sort(b.begin(),b.end(),cmp);
    for (int i=0;i<k;i++)	//在原数组中将排序后的数组的前x个置为-1，代表在这回合使用塔子起飞
        a[b[i][1]]=-1;
    int ans=0,cnt=0;	//cnt代表之前用过的塔子起飞次数，res代表最后受到伤害的总和
    for (int i=0;i<n;i++)
        if (a[i]==-1)
            cnt+=1;	//如果使用塔子起飞，则没有伤害，更新cnt
        else
            ans+=a[i]-cnt;	//不使用圣光则恢复cnt点塔子起飞，
    cout<<max(ans,1)<<endl;
    return 0;
}

java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

class test {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = scanner.nextInt();
		List<List<Integer>> b = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			List<Integer> tmp = new ArrayList<>();
			tmp.add(a[i]);
			tmp.add(i);
			b.add(tmp);
		}
		Collections.sort(b, new Comparator<List<Integer>>() {	//重写排序函数，按照 第一维-第二维 排序，即 v[i]-i
			public int compare(List<Integer> x, List<Integer> y) {
				if (x.get(1) - x.get(0) > y.get(1) - y.get(0))
					return 1;
				return -1;
			}
		});
		for (int i = 0; i < k; i++)	//在原数组中将排序后的数组的前x个置为-1，代表在这回合使用塔子起飞
			a[b.get(i).get(1)] = -1;
		int ans = 0, cnt = 0;	//cnt代表之前用过的塔子起飞次数，res代表最后受到伤害的总和
		for (int i = 0; i < n; i++)
			if (a[i] == -1)	//如果使用塔子起飞，则没有伤害，更新cnt
				cnt++;
			else	//不使用塔子起飞则恢复cnt点体力，
				ans += a[i] - cnt;
		System.out.println(Math.max(ans, 1));
	}
}

js

var in1 = readline().split(' ')
var n = parseInt(in1[0]), k = parseInt(in1[1])
var v = readline().split(' ')
var tmp = []		//用于排序的数组
for(var i = 0 ; i < n ; i++) {
	//按照上面的推导，回合数从1开始，第二维应该存i+1，但是不影响排序所以存i即可
    tmp.push([parseInt(v[i]), i])
}
tmp.sort(function(a,b){	//重写排序函数，按照 第一维-第二维 排序，即 v[i]-i
    return (b[0] - b[1]) - (a[0] - a[1])
})
for(var i = 0 ; i < k ; i++) {	//在原数组中将排序后的数组的前x个置为-1，代表在这回合使用塔子起飞
    v[tmp[i][1]] = -1
}
var res = 0, cnt = 0		//cnt代表之前用过的塔子起飞次数，res代表最后受到伤害的总和
for(var i = 0 ; i < n ; i++) {
    if(v[i] == -1) {
        cnt += 1		//如果使用塔子起飞，则没有伤害，更新cnt
    } else {
        res += parseInt(v[i]) - cnt	//不使用塔子起飞则恢复cnt点体力，
    }
}
console.log(Math.max(res, 1))

go

package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)

	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}

	b := make([][]int, n)
	for i := 0; i < n; i++ {
		// Store i instead of i+1 since it doesn't affect sorting
		b[i] = []int{a[i], i}
	}

	sort.SliceStable(b, func(i, j int) bool {
		return b[i][0]-b[i][1] > b[j][0]-b[j][1]
	})

	for i := 0; i < k; i++ {
		a[b[i][1]] = -1
	}

	ans := 0
	cnt := 0
	for _, val := range a {
		if val == -1 {
			cnt++
		} else {
			ans += val - cnt
		}
	}

	if ans < 1 {
		fmt.Println(1)
	} else {
		fmt.Println(ans)
	}
}

题目内容

塔子最近在玩一款闯关游戏,其共有 $m$ 个回合，塔子有个技能：塔子起飞。总共可以使用 $x$ 次， 以下是对这个技能的简介:

1.每回合使用不超过一次。

2.如果在某一个回合使用了塔子起飞，那么塔子免疫该回合受到的所有伤害，并且在之后没有使用该技能的回合中每回合恢复 $1$ 点体力值

3.技能的效果可以叠加

以下是对塔子起飞技能的案例说明:

前两个回合都释放了一次塔子起飞，那么第三个回合就会恢复 $2$ 点体力。

通关条件:

塔子只需要在 $m$ 个回合后体力大于等于 $0$ ，即可通关。

问题定义:

请问塔子初始最少需要多少体力。(初始体力应该大于等于 $1$ , 过程中允许部分时刻体力小于 $0$ )

输入描述

输入第一-行包含两个整数 $m$ 和 $x$ ，分别表示回合数和塔子起飞使用次数。$(1 \leq m,x \leq 10^5)$

输入第二行包含 $m$ 个整数，分别表示在第 $1$ 个回合到第 $m$ 个回合中，塔子受到伤害，每回合造成的伤害不超过 $10^5$。

输出描述

输出仅包含一个整数，即最少需要的体力值。

样例

输入

5 2
7 3 2 6 5

输出

6