题解

题面描述

给定一个为期$n$天的小吃节，每天都有一个摊位，摊位第$i$天产生的营业额为$r_i$，消耗的人力为$m_i$。管理方希望选取一段连续的天数区间，使得这段区间内的总人力不超过$K$，且总营业额最大。求该最大总营业额。

思路

1. 由于所有$m_i>0$，我们可以用双指针（滑动窗口）维护一个左指针$L$和右指针$R$，窗口表示天数区间 $[L,R]$。

2. 用两个变量记录当前窗口的总人力cur_man和总营业额cur_rev。

3. 初始令$L=1$,$R=0$,cur_man=0,cur_rev=0，最大答案$ans=0$。

4. 不断将右指针$R$向右移入一天：

   • 更新cur_man+!=m_R，cur_rev+!=r_R。

   • 当cur_man>K时，说明超出人力，上移左指针直至cur_man<=K：

     

   • 此时窗口合法，更新ans=max(ans,cur_rev)。

5. 遍历结束后${ans}$即为所求。整体时间复杂度为$O(n)$。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, K;
    cin >> n >> K;  // 输入天数 n 和人力上限 K

    vector<int> r(n), m(n);
    for (int i = 0; i < n; i++) {
        cin >> r[i] >> m[i];  // 第 i 天的营业额 r[i] 和人力 m[i]
    }

    long long ans = 0;       // 最终答案：最大营业额
    long long cur_rev = 0;   // 当前窗口总营业额
    long long cur_man = 0;   // 当前窗口总人力
    int L = 0;               // 窗口左指针

    for (int R = 0; R < n; R++) {
        cur_rev += r[R];
        cur_man += m[R];
        // 如果人力超限，则右移左指针收缩窗口
        while (cur_man > K) {
            cur_rev -= r[L];
            cur_man -= m[L];
            L++;
        }
        ans = max(ans, cur_rev);
    }

    cout << ans << "\n";
    return 0;
}

Python

def max_revenue(n, K, revenues, manpowers):
    ans = 0            # 最终最大营业额
    cur_rev = 0        # 窗口当前营业额
    cur_man = 0        # 窗口当前人力
    L = 0              # 左指针

    for R in range(n):
        cur_rev += revenues[R]
        cur_man += manpowers[R]
        # 当人力超出上限时，移动左指针
        while cur_man > K:
            cur_rev -= revenues[L]
            cur_man -= manpowers[L]
            L += 1
        ans = max(ans, cur_rev)
    return ans

if __name__ == "__main__":
    n, K = map(int, input().split())
    revenues = []
    manpowers = []
    for _ in range(n):
        r, m = map(int, input().split())
        revenues.append(r)
        manpowers.append(m)
    print(max_revenue(n, K, revenues, manpowers))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();    // 天数
        int K = sc.nextInt();    // 人力上限

        int[] r = new int[n];    // 营业额数组
        int[] m = new int[n];    // 人力数组
        for (int i = 0; i < n; i++) {
            r[i] = sc.nextInt();
            m[i] = sc.nextInt();
        }

        long ans = 0;            // 最终最大营业额
        long curRev = 0;         // 当前窗口总营业额
        long curMan = 0;         // 当前窗口总人力
        int L = 0;               // 左指针

        for (int R = 0; R < n; R++) {
            curRev += r[R];
            curMan += m[R];
            // 若人力超限，则收缩窗口
            while (curMan > K) {
                curRev -= r[L];
                curMan -= m[L];
                L++;
            }
            ans = Math.max(ans, curRev);
        }

        System.out.println(ans);
        sc.close();
    }
}

题目内容

某市场举办小吃节，小吃节持续$n$天，每天都会有不同的小吃摊位入驻，每个摊位每天在投入一定的人力之后产生一定的营业额。

管理方希望在小吃节期间选择连续的若干天，使得这些天的总营业额最大。但是由于人力限制，选择这些天中总的人力不超过$K$人天。

请你计算出满足条件的最大营业额。

输入描述

第$1$行输入$2$个数字，分别是小吃节持续天数$n(0<n<100)$，总的人力$K$人天$(0<K<10000)$

第$2$行到第$n+1$行，每一行输入$2$个数字，代表每天的营业额$(0<j<10000)$以及人力$m$人天$(0<m<1000，m<K)$

输出描述

在不超过$K$人天总人力限制的情况下，输出最大连续营业的营业额。

样例1

输入

6 6
3 1
1 2
5 1
2 3
7 2
4 4

输出

14

说明

小吃节持续$6$天，总人力限制$6$人天，

$1.$第$1$天营业额为$3$，人力为$1$

$2.$第$2$天营业额为$1$，人力为$2$

$3.$第$3$天营业额为$5$，人力为$1$

$4.$第$4$天营业额为$2$，人力为$3$

$5.$第$5$天营业额为$7$，人力为$2$

$6.$第$6$天营业额为$4$，人力为$4$

选择第$3$天到第$5$天，人力是$1+3+2=6$，不超过$6$人天，营业额总和为$5+2+7=14$，这是满足人力不超过$6$人天情况下的最大营业额。

样例2

输入

4 7
10 1
20 2
30 3
40 4

输出

70

说明

小吃节持续$4$天，总人力限制$7$人天。

$1.$第$1$天营业额为$10$，人力为$1$

$2$.第$2$天营业额为$20$，人力为$2$

$3.$第$3$天营业额为$30$，人力为$3$

$4.$第$4$天营业额为$40$，人力为$4$