题解：P13521 [KOI 2025 #2] 包

ryf2011 · 2025-07-31 22:48:05 · 题解

0.更新日志

2025.8.3：修正了一处笔误，并修改、润色内容。

1.题目思路

由于小偷会取 K 个数且和最小，我们容易想到排序。先将原数列排序，此时前 K 个数即为最小和。

但是，商户每次还会取出若干个（可能为零）物品装入包中。什么时候答案最大呢？

我们考虑维护一个指针 l，指向当前商户决定是否带走的物品（在 l 之前的物品一定会选，否则将留下小的数，不优），由于背包的容量是有限的，我们考虑把物品尽量装入背包，由于我们已经对数列排序，那么后面的数一定比前面的数大，所以答案更优。

但是，这个方法无法通过样例#3！为什么呢？考虑样例#3中，x = 2 时，显然只装入第 1 个物品比装入前 2 个物品更优，而按照我们的思路却选择了后者。

此时，我们发现，商户不一定要把包装满。

由于 K 的值不变，我们可以提前计算出数列中每 K 个数（即 1 \sim K,2 \sim K+1,\cdots,N-K+1 \sim N）的和，计算答案时，在保证装入背包的物品重量不超过当前容量上限的情况下（利用前缀和数组 sum 解决，即 \texttt{sum[l]}），找到所有满足条件的选法中的最大值并输出。

:::warning[本题数据范围]{open}

十年OI一场空，（下一句你懂得）。

本题的前缀和数组，以及答案变量都需要开 \texttt{long long}！ :::

2.代码

注：代码仅供参考。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int max_n=5005;
int n,k,c,a[max_n],l;
long long sum[max_n],ksum[max_n],ans; //开 long long！
int main(){
    scanf("%d %d %d",&n,&k,&c);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1); //排序
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i]; //计算前缀和
    }
    for(int i=k;i<=n;i++){
        ksum[i]=sum[i]-sum[i-k]; //K个数的和
    }
    for(int i=1;i<=c;i++){
        while(sum[l]<=i&&l<=n-k){ //保证满足条件时，计算最大值（注意一开始也有可能选 0 个）
            ans=max(ans,ksum[l+k]);
            l++; //指针
        }
        printf("%lld\n",ans); //输出
    }
    return 0;
}

题解：P13521 [KOI 2025 #2] 包

0.更新日志

1.题目思路

2.代码

3.后记