讨论/《滴滴历届真题汇总》 - 2020 卷 2:简单游戏/
《滴滴历届真题汇总》 - 2020 卷 2:简单游戏
共 6 个回复

a[i]为给定的输入,则将a[1]+a[2]+...+a[i]的前缀和记为sum[i],再取max{0,sum[1],sum[2],...sum[i]}为前缀和最大值mx[i]
假如我们固定右端点,以i(i>=m)为右端点,则固定右端点的最优答案应当是前缀和sum[i]-mx[i-m]
遍历所有右端点的最优答案取最小值即为答案即可

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int mx[100005];

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]+=a[i-1];
    for(int i=1;i<=n;i++) mx[i]=max(mx[i-1],a[i]);
    int ans=0x3f3f3f3f;
    for(int i=m;i<=n;i++) ans=min(ans,a[i]-mx[i-m]);
    printf("%d",ans);
    return 0;
}

6

蛋疼,还以为没负数直接滑窗完事,结果一提交就解答错误,直到别人告诉我 0<=|ai| <=1000 里有个绝对值

思路:

  1. 先思考,如果没有至少长度为的 m 要求,这题要怎么做呢?
    原题: 53. 最大子序和
  2. 现在假设你已经理解了上面那题,就能得到状态转移方程
    dp[i]=min(dp[i1]+a[i],a[i])dp[i]=min(dp[i-1]+a[i],a[i])
  3. 现在加上至少长度为的 m 的要求,实际上还是两种情况,延长之前的一段,或者取新的一段。
  4. 延长的情况仍然是 dp[i1]+a[i]dp[i-1]+a[i]
    新的一段则是 s[i]=a[im+1]+...a[i1]+a[i]s[i]=a[i-m+1]+...a[i-1]+a[i],而这个值我们可以通过滑动窗口来减少重复计算。
    最终我们得到状态转移方程 dp[i]=min(dp[i1]+a[i],s[i])dp[i]=min(dp[i-1]+a[i],s[i])

所以有大佬知道 JavaScript 怎么提交嘛?Java 我不熟啊

代码:
复制粘贴记得删注释,中文会报错

import java.util.Scanner;

class Solution {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();

        int[] nums = new int[n];
        int left = 0;
        int right = 0;
        int sum = 0;

        // 计算第一段长度为 m 区间的和
        while (right < m) {
            sum += nums[right++] = scan.nextInt();
        }
        int min = sum;
        int dp = sum;

        while (right < n) {
            // 滑窗计算 s[i]
            int x = nums[right++] = scan.nextInt();
            sum += x - nums[left++];

            dp = Math.min(dp + x, sum);
            if(dp < min) min = dp;
        }

        System.out.println(min);
    }
}
6
import java.util.Scanner;

class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        int[] nums = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
            if (i < m) sum += nums[i];
        }
        int min = sum, pre = sum;
        for (int i = m; i < n; i++) {
            sum += nums[i] - nums[i - m];
            pre = Math.min(pre + nums[i], sum);
            min = Math.min(min, pre);
        }
        System.out.println(min);
    }
}
5

import java.util.Scanner;
public class Solution{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String line = scan.nextLine();
String[] s = line.split(" ");
int n = Integer.valueOf(s[0]);
int m = Integer.valueOf(s[1]);
int[] nums = new int [n];
String nextLine = scan.nextLine();
String[] split = nextLine.split(" ");
for(int i = 0 ; i< split.length ; i++){
nums[i] = Integer.valueOf(split[i]);
}
int min = getMinSUm(nums,m);
System.out.println(min);
}

public static int getMinSUm(int [] a , int m){
    int n = a.length;
    if(m > n){
        return 0 ;
    }
    int sum = 0 ;
    for(int index = 0 ; index <= n-m ; index ++){
        int tempSum = 0 ;
        for(int j = index ; j< m ; j++){
            tempSum += a[j];
        }
        if(index ==0 ){
            sum = tempSum;
        }else{
            sum =  sum <tempSum ? tempSum : sum;
        }
    }
    return sum;

}

}

测试用例都可以,怎么提交不行呢

初值t = 0
sumPre[i] - maxPre[i-m] > sumPre[i] - 0, if maxPre[i-m] < 0.

有没有大佬给看一下,为什么我的代码最后一个测例不能过?我感觉没有问题。

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, m, i, ans, t = INT_MIN;
    cin >> n >> m;
    vector<int> v(n);
    for (i = 0; i < n; ++i)
        cin >> v[i];
    for (i = 1; i < n; ++i)
        v[i] += v[i - 1];
    ans = v[m - 1];
    for (i = m; i < n; ++i) {
        t = max(t, v[i - m]);
        ans = min(ans, v[i] - t);
    }
    cout << ans;
    return 0;
}