我要招人

去企业版

首页 > 试题广场 >

小红的区间增加

[编程题]小红的区间增加

热度指数：243 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红拿到了一个数组，她每次可以任选一个区间，使得区间所有元素加1。小红想知道，使得数组中所有元素严格递增的最小操作次数是多少？

输入描述:

第一行输入一个正整数，代表数组的元素数量。
第二行输入个正整数，代表数组的元素。

输出描述:

一个整数，代表最小的操作次数。

示例1

输入

3
3 2 4

输出

说明

一种合法的操作如下：
第一次选择区间[2,2]，数组变成[3,3,4]。
第二次选择区间[2,3]，数组变成[3,4,5]，满足要求。
请注意，这里的区间指选了第几个数。例如区间[2,2]代表选了第二个数，区间[2,3]代表选了第二个和第三个数。

算法知识视频讲解

C/C++

小狮子老黄

首先记录一次已经输入数中的最大值，这个最大值要包括已经增加过的数。比如3 2 ，那么这个

区间的数，输入到2这个数时候，最大的数就是2+（3-2）+ 1=4. 然后，在使用一个count来记录

需要增加的次数，以后每一个新的数字都要加上这个count，也就代表着前面数增加了，后面的数

也同时在增加。
时间复杂度O(n),空间复杂度O(1).

#include <iostream>

using namespace std;

int main() {

int n;

cin>>n;

long long count = 0;

long long lastMaxNum;

cin >> lastMaxNum;

for(int i = 1; i < n; ++i) {

long long num;

cin >> num;

num += count;

long long res = lastMaxNum - num;

if(res >= 0) {

long long tempnum = num + res + 1;

count += res + 1;

lastMaxNum = max(lastMaxNum, tempnum);

}

else {

lastMaxNum = max(lastMaxNum, num);

}

printf("%lld", count);

return 0;

}

// 64 位输出请用 printf("%lld")

发表于 2023-10-01 17:40:15 回复(0)

愉快的猕猴桃在泡池子

#include <iostream>
using namespace std;
/**
*   首先第一个点肯定不提升
*   1、考虑第二个点怎么提升：假设对于第二个点的一个提升区间是[2,k]，那不如直接提升
*        区间[2,n]。因为反正要把k+1往后的都提升得比k高，既然k都提升了，则把后
*        面的一同提升也没有坏处，证明是： 
*       （假设最优提升策略的某个提升区间是[2,k]，我们把该区间改为[2,n]，其它
*        提升区间不变，则结果数组的[k+1,n]部分都升高了同一个值，仍然是严格递
*        增的，因此也是一个最优提升策略）。 
*   类似地，往后每个点开始的提升区间，都不妨直接延伸到n。 
*   所以可以认为任何一个提升区间都是[t,n]的形式，并且多个相同的[t,n]可以合并为一个。 
*
*   2、提升[t,n]，对于区间[t,n]的点的相对高度没有影响，
*       因此区间[t+1,n]要提升的高度，
*        1）如果arr[t+1]<=arr[t]的话，其实就是arr[t+1]-arr[t]+1。
*        2）否则就不用专门提升该区间。
*/
int main() {
    int n;
    long count = 0;
    cin>>n;
    long prev,tmp;
    cin>>prev;
    for(int i=1;i<n;i++){
        cin>>tmp;
        if(prev>=tmp)
            count+=prev-tmp+1;
        prev=tmp;
    }
    cout<<count;
}
// 64 位输出请用 printf("%lld")

发表于 2023-04-26 13:42:26 回复(0)

牛客717689011号

这题目需要换个头思考，因为按照题目原本的意思，我们去解，会发现一个问题，它的区间操作是可以影响后续的数的。所以我们换个头，将输入数组倒序，然后求它成为严格递减数组的操作次数，原因是我们对于a[i]到a[max]的操作，不会影响a[i-1]的值(这里a是原输入数组顺序)，倒序就是a[0]-a[k]的操作，不会影响a[k+1]。那题目就很简单了，假设倒序数组前k个数字已经严格递减，新增一个数当作a[k]，只要计算a[k]- a[k-1]的差值+1就行了(total是总操作数)

package main

import "fmt"

var total = 0 //总操作数

func main() {
	var num int
	fmt.Scan(&num)
	a := make([]int, num)
	for i := 0; i < num; i++ {
		fmt.Scan(&a[i])
	}
	// 倒置
	for i := 0; i < num/2; i++ {
		a[i], a[num-i-1] = a[num-i-1], a[i]
	}
	fmt.Println(a)
	for i := 1; i < num; i++ {
		if a[i] >= a[i-1] { // 新加入的a[i]不会受到a[i-1]的影响，下次计算保持原值，就很方便
			total += a[i] - a[i-1] + 1
		}
	}
	fmt.Println(total)
}

发表于 2023-04-18 15:21:52 回复(0)

尼古拉nicola

#include <iostream>

using namespace std;

//贪心：考虑从后往前排的情景，当num[i-1]>=nums[i],对index>=i区间的nums[index]都进行+1直到num[i-1]<nums[i]就可得出递推公式

int main() {

int n, pre, cur;

long res=0;

cin>>n>>pre;

--n;

while(n--){

cin>>cur;

if(cur<=pre)

res+=pre-cur+1;

pre=cur;

}

cout<<res;

}

发表于 2023-03-17 21:36:46 回复(1)

Java

高大的牛油在投简历

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

long [] array = new long[n];

for (int i = 0; i < n; i++) {

array[i] = in.nextLong();

}

long res = 0;

for (int i = 1; i < n; i++) {

if (array[i] <= array[i - 1]) {

res += array[i - 1] - array[i] + 1;

}

System.out.println(res);

}

发表于 2023-03-16 16:47:37 回复(0)

梅老板的粉

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n, 0);
    for (auto&e: v) cin >> e;
    int i = 0;
    int64_t ret = 0;
    while (i < v.size()-1) {
        if (v[i] >= v[i+1])
            ret += v[i] - v[i+1] + 1;
        i++;
    }
    std::cout<<ret<<std::endl;
}
// 64 位输出请用 printf("%lld")

发表于 2023-03-16 01:30:30 回复(0)

ԅ(¯ㅂ¯ԅ)卡西莫多

# 贪心：区间严格递增的最少操作次数
# 4 2 9 19 2 -->将后面的数都递增：4 5 12 22 5 等价于只递增一个数：4 5 9 19 2
# 因为他们的差值不变
# 只需要找到第一个开始减小的位置，然后计算差值
n = int(input())
line1 = input()
num = list(map(int, line1.split()))
count = 0
dif = 0
for i in range(1,len(num)):
    if num[i] <= num[i-1]:
        dif = num[i-1] - num[i] + 1
        count += dif
print(count)

发表于 2023-03-09 17:34:22 回复(0)