[PAT-A] 1044 Shopping in Mars

Java

测试点2、3、5超时

import java.util.Scanner;

public class Main {

    static final int N = 100010;
    static final int INF = 0x3f3f3f3f;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int M = sc.nextInt();
        int[] s = new int[N];

        for (int i = 1; i <= n; ++i) {
            s[i] = sc.nextInt();
            s[i] += s[i - 1];
        }

        int res = INF;
        for (int i = 1, j = 0; i <= n; ++i) {
            while (s[i] - s[j + 1] >= M) j++;
            if (s[i] - s[j] >= M) res = Math.min(res, s[i] - s[j]);
        }

        for (int i = 1, j = 0; i <= n; ++i) {
            while (s[i] - s[j + 1] >= M) j++;
            if (s[i] - s[j] == res) {
                System.out.println((j + 1) + "-" + i);
            }
        }

        sc.close();
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

int n, M;
int s[N];

int main() {
    scanf("%d%d", &n, &M);

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }

    int res = INF;
    for (int i = 1, j = 0; i <= n; ++i) {
        while (s[i] - s[j + 1] >= M) j++;
        if (s[i] - s[j] >= M) res = min(res, s[i] - s[j]);
    }

    for (int i = 1, j = 0; i <= n; ++i) {
        while (s[i] - s[j + 1] >= M) j++;
        if (s[i] - s[j] == res) printf("%d-%d\n", j + 1, i);
    }
    return 0;
}