题解 | #经此一役小红所向无敌#

更好的阅读体验

D.

看到数据范围 ，遍历一遍是没有问题的。

这启发我们枚举吃桃子的日子是哪一天。

对于 数组和 数组，可以采用前缀和，在判断该天是否吃桃子时起到 计算的帮助。

时间复杂度 。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 111111;
const int inf = 1e10;

int a[N], b[N], n, k;

ll preA[N], preB[N]; 

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

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

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

    preA[0] = 0, preB[0]= 0;

    for (int i = 1; i <= n; i ++) {
        preA[i] = preA[i - 1] + a[i];
        preB[i] = preB[i - 1] + b[i];
    }

    //for (int i = 1; i <= n; i ++) {
    //    cout << "preA[" << i << "]:" << preA[i] << " ";
    //    cout << "preB[" << i << "]:" << preB[i] << endl;
    //}

     ll mxA = -inf, mnB = inf;

    int id = 0;

    for (int i = 1; i <= n - k + 1; i ++) {
        ll tpA = preA[i + k - 1] - preA[i - 1];
        ll tpB = preB[i + k - 1] - preB[i - 1];

        //cout << "mnB:" << mnB << " " << "tpB:" << tpB << endl;

        if (tpA > mxA) {
            id = i;
            mxA = tpA;
            mnB = tpB;
        }

        else if (tpA == mxA) {
            if (tpB < mnB) {
                id = i;
                mxA = tpA;
                mnB = tpB;
            }
        }
    }

    //cout << mxA << " " << mnB;

    //cout << "mnB:" << mnB;

    printf ("%d", id);

    return 0;
}