首页 > 试题广场 >

种花

[编程题]种花
  • 热度指数：3172 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
公园里有 n 个花园，初始时每个花园里都没有种花，园丁将花园从 1 到 n 编号并计划在编号为 i 的花园里恰好种 Ai 朵花，他每天会选择一个区间 [L，R]（1≤L≤R≤N）并在编号为 L 到 R 的花园里各种一朵花，那么园丁至少要花多少天才能完成计划？

数据范围： ，

输入描述:
第一行包含一个整数 n 。

第二行包含 n 个空格隔开的数 ai 到 an。


输出描述:
输出完成计划所需的最少天数。
示例1

输入

5
4 1 8 2 5

输出

14
示例2

输入

5
1 1 1 1 1

输出

1
算法知识视频讲解
添加回答
白色纯度头像 白色纯度
我来献丑了，希望大家可以发表自己的看法，多多完善思路，可以看这篇博客，提提自己的观点。
https://blog.csdn.net/weixin_42564710/article/details/97646339 
if __name__=='__main__':
    n = int(input())
    num = list(map(int,input().split()))
    count = 0
    for i in range(n-1):
        count += max(num[i]-num[i+1],0)
    print(count+num[-1])

发表于 2019-07-29 16:18:31 回复(3)
练习时长两年半的Java练习生头像 练习时长两年半的Java练习生

贪心法

public class Main {
    public static void main(String[] args) {
        java.util.Scanner sc = new java.util.Scanner(System.in);
        int N = sc.nextInt();
        int[] target = new int[N];
        for (int i = 0; i < N; ++i) {
            target[i] = sc.nextInt();
        }
        int cnt = 0;
        for (int i = 1; i < N; ++i) {
            if (target[i - 1] > target[i]) {
                cnt += target[i - 1] - target[i];
            }
        }
        System.out.println(cnt + target[N - 1]);
    }
}
编辑于 2019-06-29 21:09:31 回复(2)
hxdk头像 hxdk
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int pre=0,res=0;
    for(int i=1;i<=n;i++)
    {
        int f;
        cin>>f;
        res=res+max(f-pre,0);
        pre=f;
    }
    cout<<res<<endl;
    return 0;
}
发表于 2019-05-24 09:54:35 回复(2)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,x,s=0;
    cin>>n;
    int a[n+1];
    for(int i=0;i<n;i++)
        cin>>a[i];
    a[n] = 0;
    for(int i=0;i<n;i++)
        s += max(0, a[i]-a[i+1]);
    cout<<s<<endl;
    return 0;
}

发表于 2019-09-19 07:23:21 回复(0)
pein531头像 pein531
先理解一下题中给的例子：4 1 8 2 5
第1天园丁对[0,4]区间种一朵花，就变为3 0 7 1 4，由于区间[L,R]是连续的，此时花园1已经达成任务了，园丁就必须从被0分隔开的左右两部分选一个接着进行相同的种植过程。
第2天选择左边的3，即区间[0,0]，将花园0的任务完成需要3天（2~4天）。
第5天又到右边的7 1 4来，对这个[2,4]区间内的花园都种1朵花，就得到6 0 3，又被0分成了左右两个部分，这两个部分的任务又只能分两步来完成。
选择左边，再花6天（6~11天）完成任务，得到0 0 0 0 3，再花3天（12~14天）完成最后一个花园的任务，一共14天。 
n = int(input())
arr = list(map(int, input().strip().split()))
days = arr[-1]
for i in range(n - 1):
    days += max(0, arr[i] - arr[i + 1])
print(days)
因为每次被0分隔成两部分的时候都是选择的左边，所以从0遍历到n-2，每次加上arr[i]-arr[i+1]，最后加上arr[n-1]；如果每次选择右边，那就是从1开始遍历，每次加上arr[i]-arr[i-1]，最后加上arr[0]。
对题目的例子来说，如果arr[i+1]<arr[i]，就需要先把arr[i+1]变成0，然后挑它左边的arr[i]单独完成就需要加上它们的高差arr[i]-arr[i + 1]（这是单独完成左边任务时花费的天数）。最后一个元素arr[n-1]没有右边的元素与它做差，但是之前每次将arr[i+1]变成0的时候，arr[n-1]也被减掉了相同的大小，所以最后只需要加上arr[n-1]把天数补齐即可，它已经被分解到每次得到分隔符0的时候了。
另外，如果每次都选择0右边的任务，代码如下： 
n = int(input())
arr = list(map(int, input().strip().split()))
days = arr[0]
for i in range(1, n):
    days += max(0, arr[i] - arr[i - 1])
print(days)


编辑于 2021-02-02 11:54:01 回复(0)
美团内推（专业正版）头像 美团内推（专业正版）
//动态规划，
//（1）表示：1~i个花坛需要dp[i] 天
//（2）初值：dp[1] = p[1],只有第一个花坛的时候，用p[1]天
//（3）状态转移：当后一个花坛p[i]比前一个p[i-1]小,dp[i] = dp[i-1]
//后一个花坛容量更大，前边的已经覆盖不到，则dp[i] = dp[i-1]+（p[i]-p[i-1]）;
//（4）输出：dp[n] 
int main()
{
    int N;
    cin >> N;
    int *p = new int[N + 1];
    for(int i = 1; i <= N; i++)
    {
        cin >> p[i];
    }
     
    int *dp = new int[N + 1];
    dp[1] = p[1];
    for(int i = 2; i <= N; i++)
    {
        if(p[i] <= p[i-1])
        {
            dp[i] = dp[i-1];
        }
        if(p[i] > p[i-1])
        {
            dp[i] = dp[i-1] + p[i] - p[i-1];
        }
    }
    cout << dp[N] << endl;
    delete []p;
    delete []dp;
    return 0;
}


发表于 2020-07-05 12:29:56 回复(0)
Python
Jancydc头像 Jancydc
方法一：动态规划
dp[i]:前i个编号花园里的花最少需要的天数
dp[0] = flowers[0]
状态转移方程：
dp[i]= dp[i-1]                         (flowers[i]<flowers[i-1])
dp[i]=dp[i-1]+flowers[i]-flowers[i-1]  (flowers[i]>=flowers[i-1])
def solution(flowers):
    dp = [0]*len(flowers)
    dp[0] = flowers[0]  # 初始化dp
    for i in range(1, len(flowers)):
        if flowers[i]<flowers[i-1]:
            dp[i] = dp[i-1]
        else:
            dp[i] = dp[i-1]+flowers[i]-flowers[i-1]
    return dp[-1]
if __name__ == '__main__':
    n = int(input().strip())
    flowers = list(map(int, input().strip().split()))
    print(solution(flowers))
方法二：贪心，因为相邻的花园可以同时被浇，因此考虑计算相邻的差值，注意不要遗漏数组最后一个数，因为它没有被计算差值 
def solution2(flowers):
    res = []
    for i in range(len(flowers)-1):
        if flowers[i]>flowers[i+1]:
            res.append(flowers[i]-flowers[i+1])
    res.append(flowers[-1])
    return sum(res)

if __name__ == '__main__':
    n = int(input().strip())
    flowers = list(map(int, input().strip().split()))
    print(solution2(flowers))
发表于 2020-06-26 13:24:05 回复(0)
算法才是灵魂头像 算法才是灵魂

思路一：递归

n = int(input())
l = list(map(int, input().split()))
res = 0
L = [l]
while len(L) > 0:
    next = []
    for l in L:
        minN = min(l)
        tmp = []
        res += minN
        for e in l:
            if e == minN:
                if len(tmp) != 0:
                    next.append(tmp)
                    tmp = []
            else:
                tmp.append(e-minN)
        if len(tmp) > 0:
            next.append(tmp)
    L = next
print(res)

但是上述解法只能A65%的数据

参考了大佬前排大佬的思路
思路二：贪心
因为相邻的差值是一定需要加到我们最后的结果中的，这里解释一下为什么加上最后一个数，是因为我们在循环中，没有计算最后的花朵的数量，而且最后一个园区的花朵，也必定要种l[-1]天

n = int(input())
l = list(map(int, input().split()))
res = 0
for i in range(n-1):
    res += max(0, l[i] - l[i+1])
print(res + l[-1])
发表于 2019-08-23 22:55:52 回复(0)
hzdms头像 hzdms 
n = int(input())
nums = list(map(int, input().split()))

cnt = 0
for i in range(len(nums) - 1):
    cnt += max(0, nums[i] - nums[i + 1])
cnt += nums[-1]
print(cnt)
实际上这样做会制造一个单调递增序列，
比如题目用例，[4, 1, 8, 2, 5]，如果我们在执行上面的代码同时update整个序列，会得到
1: [1, 1, 8, 2, 5], sum = 3
2: [1, 1, 8, 2, 5], sum = 3
3: [1, 1, 2, 2, 5], sum = 3 + 6
此时序列已经递增，最后一个数字是5，那么5天就可以种完， sum = 3 + 6 + 5 = 14.

举一个复杂的例子，[5, 3, 7, 1, 6]
1: [3, 3, 7, 1, 6], sum = 2
2: [3, 3, 7, 1, 6], sum = 2
下一步比较特殊，因为第三位之前的序列是单调递增的，我们执行7 - 1天种植之后，第一位和第二位的3也会变成1
3: [1, 1, 1, 1, 6], sum = 2 + 6
4: 此时序列单调递增，sum = 2 + 6 + 6 = 14。其实也可以这样考虑，在数列最后添加0，变成[1, 1, 1, 1, 6, 0], 最后执行 6 - 0天种植, 数列会全部归零，sum = 2 + 6 + 6 = 14.
发表于 2019-09-06 05:57:19 回复(4)
Hale201905051125960头像 Hale201905051125960
DP思路，（1）表示：1~i个花坛需要dp[i] 天
                （2）初值：dp[0] = nums[0],只有第一个花坛的时候，用nums[0]天
                 （3）状态转移：当后一个花坛nums[i]比前一个nums[i-1]小,dp[i] = dp[i-1]
                                           后一个花坛容量更大，前边的已经覆盖不到，则
                                        dp[i] = dp[i-1]+（nums[i]-nums[i-1]）;
                 （4）输出：dp[n-1] 
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
    int n;
    cin>>n;
    vector<int> nums;
    vector<int> dp(n,0);
    int temp;
    for(int i = 0;i<n;i++)
    {
        cin>>temp;
        nums.push_back(temp);
    }
    dp[0] = nums[0];
    for(int i=1;i<n;i++)
    {
        if(nums[i]<=nums[i-1])
            dp[i] = dp[i-1];
        else
            dp[i] = dp[i-1]+nums[i]-nums[i-1];
    }
    cout<<dp[n-1];
}


发表于 2020-03-13 00:23:32 回复(3)
牛客7587184号头像 牛客7587184号
单调栈 
def solve(n,nums):
    """
    单调栈
    栈内只存储递增元素
    时间复杂度O(n)
    :param n:
    :param nums:
    :return:
    """
    nums.append(0)
    stack = []
    res = 0
    for i in range(n+1):
        if not stack or stack[-1]<=nums[i]:
            stack.append(nums[i])
        else:
            res += stack[-1]-nums[i]
            while stack and stack[-1]>nums[i]:
                stack.pop()
            stack.append(nums[i])
    print(res)

n = int(input())
nums = [int(x) for x in input().split()]
solve(n,nums)

发表于 2019-05-16 22:21:06 回复(0)
筱伞不是伞！头像 筱伞不是伞！ 
import sys
n = int(input().split()[0])
num = list(map(int,sys.stdin.readline().split()))

# 单调栈,给以前的峰值进行浇花
stack = []
count = 0
for i in num:
    if len(stack) == 0:
        stack.append(i)
        continue
    elif stack[-1] <= i:
        stack.append(i)
        continue
    else:
        count += stack[-1] - i
        while(len(stack)!=0):
            if stack[-1] > i:
                stack.pop()
            else:
                break
        stack.append(i)
if len(stack) !=0:
    count += stack[-1]

print(count)


发表于 2023-04-07 18:42:06 回复(0)
Java
只会暴力做题头像 只会暴力做题
分片暴力 
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] ns = new int[n];
        for (int i = 0; i < n; i++) {
            ns[i] = in.nextInt();
        }
        int ans = 0;
        // 找到第一个大于0的数
        int left = findLeft(ns, 0);
        while (left != -1) {
            // 从left开始，更新ns数组
            ans += func(ns, left);
            // 找到第一个大于0的数
            left = findLeft(ns, left);
        }
        System.out.println(ans);
    }

    private static int func(int[] ns, int left) {
        int min = ns[left];
        int right = ns.length;
        // 第一次循环，维护min值和right
        for (int i = left + 1; i < ns.length; i++) {
            if (ns[i] == 0) {
                right = i;
                break;
            }
            if (ns[i] < min) {
                min = ns[i];
            }
        }
        // 第二次循环，更新ns数组
        for (int i = left; i < right; i++) {
            ns[i] -= min;
        }
        return min;
    }

    private static int findLeft(int[] ns, int pst) {
        // 找到left，即第一个大于0的数，若没有则返回-1
        for (int i = pst; i < ns.length; i++) {
            if (ns[i] > 0) {
                return i;
            }
        }
        return -1;
    }

}


发表于 2022-08-12 17:00:31 回复(0)
花泽类的泪头像 花泽类的泪 
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	ans := 0
	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	for i := 1; i < n; i++ {
		if a[i-1] > a[i] {
			ans += a[i-1] - a[i]
		}
	}
	ans += a[n-1]
	fmt.Println(ans)
}

发表于 2022-08-04 23:49:42 回复(0)
JavaScript
牛客732046691号头像 牛客732046691号
let num = parseInt(read_line());
let line = '';
let newArr = [];
while(line = read_line()){
  newArr = line.split(' ').map(Number);
}
// 这里要理解题意：每天选择一个区间浇花，用最少的时间完成自己的浇花目标，也就是一个策略问题
// 这里要注意的是不能选最大区间一直种花，因为每个花园的种花目标不一致，这样会超出目标值
// 上面的数组中各个元素就是每个花园需要种花的数量
// 设编号1到i-1花坛种完需要dp[i]天 输出dp[num-1]
 function minTime(num,target){
   let dp = new Array(num).fill(0);
   dp[0] = target[0];
   for(let i=1;i<num;i++){
     if(target[i]<target[i-1]){
       dp[i] = dp[i-1];
     }else{
       dp[i] = dp[i-1] + target[i]-target[i-1];
     }
   }
   console.log(dp[num-1]);
 }
minTime(num,newArr);
ps:只能ac36% 也不知道啥毛病
发表于 2022-06-17 21:09:07 回复(0)
牛客763745392号头像 牛客763745392号 
import java.util.*;

public class Main
{
    public static void main(String args[])
    {
        int n;
        // 动态规划
        // dp[i] 表示种满当前花园需要的天数，p[i] 表示需要种的花的数量
        // p[i] > p[i-1] dp[i] = dp[i-1] + p[i] - p[i-1]
        // p[i] <= p[i-1] dp[i] = dp[i-1]
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[] p = new int[n];
        int[] dp = new int[n];
        
        for(int i = 0; i < n; i++)
        {
            int t = sc.nextInt();
            p[i] = t;
            
            if(i == 0)
                dp[0] = p[0];
            else
                dp[i] = p[i] <= p[i-1] ? dp[i-1] : dp[i-1] + p[i] - p[i-1];
        }
        System.out.println(dp[n-1]);
    }
}

发表于 2021-03-18 19:29:01 回复(0)
Finley20头像 Finley20 
import java.util.Scanner;
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner de=new Scanner(System.in);
        while(de.hasNext()){
            int n=de.nextInt();
           
            int[] res=new int[n];
            for(int i=0;i<n;i++){
                res[i]=de.nextInt();
            }
            Stack<Integer> stack=new Stack<>();
            stack.push(res[0]);
            int count=0;
            for(int i=1;i<n;i++){
                while(!stack.isEmpty()&&res[i]<stack.peek()){
                    int d=stack.pop();
                    int d1=res[i];
                    if(!stack.isEmpty()){
                        d1=Math.max(d1,stack.peek());
                    }
                    count+=d-d1;
                }
                    stack.push(res[i]);
                }
            while(!stack.isEmpty()){
                int f=stack.pop();
                if(!stack.isEmpty()){
                    count+=f-stack.peek();
                }else{
                    count+=f;
                }
            }
            System.out.println(count);
            }
        }
    }


发表于 2020-08-14 16:20:36 回复(0)
kkk大人头像 kkk大人
思路：需要把数列搞成单调递减的
41825
41825（8-1=7次）
41825（5-2=3次）
00000（4次） 

    {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[] data=new int[n]; 
        
        for(int i=0;i<n;i++)
        {
            data[i]=sc.nextInt();
        }
        
        int res=0;
        for(int i=0;i<n-1;i++)
        {
            if(data[i]<data[i+1])
            {
                res=res+(data[i+1]-data[i]);
            }
        }
        res+=data[0];
        
        System.out.println(res);
    }


递归：case通过率为65.00%，有数组越界现象？？？ 
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[] data=new int[n]; 
        
        for(int i=0;i<n;i++)
        {
            data[i]=sc.nextInt();
        }
        
        int res = helper(data);
        System.out.println(res);
    }

    static int helper(int[] data)
    {
        if(data.length<=1)
            return data[0];
        int min = Integer.MAX_VALUE;
        int cut=0;
        for(int i=0;i<data.length;i++)
        {
            if(data[i]<min)
            {
                min=data[i];
                cut=i;
            }
        }
        for(int i=0;i<data.length;i++)
        {
            data[i]-=min;
        }
        int res=min;
        
        if(cut>0)
        {
            res+=helper(Arrays.copyOfRange(data,0,cut));
        }
        if(cut<data.length-1)
        {
            res+=helper(Arrays.copyOfRange(data,cut+1,data.length));
        }
        return res;
    }


发表于 2020-07-27 17:38:43 回复(0)
Java
何止hz头像 何止hz 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Author: coderjjp
 * @Date: 2020-05-11 12:40
 * @Description: 种花
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] line2 = br.readLine().split(" ");
        int A[] = new int[N];
        for (int i = 0; i < N; i++)
            A[i] = Integer.parseInt(line2[i]);
        int cur = 0;
        int ans = 0;
        while (cur < N && A[cur] == 0)//找到第一个不为0
                cur++;
        while (cur < N){
                        //但下面这个循环耗时比较长
            for (int j = cur; j < N && A[j] > 0; j++)//从cur开始向后种，能种的全种上
                A[j]--;
            ans++;//天数加1
            while (cur < N && A[cur] == 0)//种完一遍后从cur向后找到下一个不为0的待种花园
                cur++;
        }//cur = N, 说明已全部种上，跳出循环,贪心法
        System.out.println(ans);
    }
}
参考网友的代码，动态规划实现，效率确实相当高。 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Author: coderjjp
 * @Date: 2020-05-11 13:42
 * @Description:
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] line2 = br.readLine().split(" ");
        int A[] = new int[N];
        for (int i = 0; i < N; i++)
            A[i] = Integer.parseInt(line2[i]);
        int dp[] = new int[N];
        dp[0] = A[0];
        for (int i = 1; i < N; i++){
            if (A[i] <= A[i-1])
                dp[i] = dp[i-1];
            else
                dp[i] = dp[i-1] + (A[i] - A[i-1]);
        }
        System.out.println(dp[N-1]);
    }
}


编辑于 2020-05-11 13:54:54 回复(0)
芳华201909081440338头像 芳华201909081440338
#include<iostream>
#include<vector>
using namespace std;
vector<int> flower;
int main(){
    int N;
    int tmp;
    cin >>N;
    for(int i=0;i<N;++i){
        cin >>tmp;
        flower.push_back(tmp);
    }
    flower.push_back(0);
    int sum=0;
    for(int i=0;i<N;++i){
        sum+=max(0,flower[i]-flower[i+1]);
    }
    cout <<sum<<endl;
    flower.clear();
}

发表于 2019-09-11 09:56:55 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 数组 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 贪心 美团 2019 Java工程师
来自：美团2019年秋招部分...
上传者：小小
难度：
25条回答 8740浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号