P13512

[KOI 2025 #1] 稻草人

题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

一支带有力量 $P$ 的箭从数轴上的位置 0 向右方发射。在每个整数位置 $i$ ( $1 \le i \le N$ )，最多可以设置一个防御力为 $A_i$ 的稻草人。当箭撞到稻草人时，如果箭的力量小于或等于稻草人的防御力，箭会立即停止。反之，如果箭的力量大于防御力，箭的力量会减去 $A_i$ 并继续前进。

对于整数 $i$ ，我们将 $f(i)$ 的值定义为“为了使箭在位置 $i$ 或其左侧停止所需要的稻草人的最小数量”。如果无法使箭停止，则值为 $-1$ 。

例如，假设 $N=5, P=10$ 并且 $A_1=3, A_2=6, A_3=1, A_4=1, A_5=10$ 。所有 $f(i)$ 的值和安装的稻草人的位置如下表所示。

$i$	$f(i)$ 的值	安装的稻草人的位置
$i=1$	$-1$	不可能
$i=2$	$-1$	不可能
$i=3$	$3$	$[1, 2, 3]$
$i=4$	$3$	可选择 $[1, 2, 3]$ 或 $[1, 2, 4]$ 之一
$i=5$	$1$	$[5]$

请编写一个程序，求出对于所有 $1 \le i \le N$ 的 $i$ 的 $f(i)$ 值。

输入格式

第一行给定整数 $N$ 和箭的力量 $P$ ，以空格分隔。

第二行给定 $N$ 个整数 $A_1, A_2, \cdots, A_N$ ，以空格分隔。

输出格式

在第一行输出 $f(1), f(2), \cdots, f(N)$ 的值，以空格分隔。

输入输出样例

输入样例 #1

5 10
3 6 1 1 10

输出样例 #1

-1 -1 3 3 1

输入样例 #2

3 10
20 20 20

输出样例 #2

1 1 1

输入样例 #3

1 5
3

输出样例 #3

-1

说明/提示

限制条件

给定的所有数都是整数。
$1 \le N \le 500,000$
$1 \le P \le 10^9$
对于每个 $1 \le i \le N$ 的 $i$ ，都有 $1 \le A_i \le 10^9$ 。

子任务

(4 分) $N \le 8$
(8 分) $N \le 5000$
(8 分) 对于所有 $1 \le i \le N$ 的 $i$ ， $A_i = 1$ 。
(20 分) 对于所有 $1 \le i \le N$ 的 $i$ ， $A_i = 2$ 或 $A_i = 3$ 。
(40 分) 对于所有 $1 \le i \le N$ 的 $i$ ， $A_i \le 50$ 。
(40 分) 对于所有 $1 \le i < N$ 的 $i$ ， $A_i \le A_{i+1}$ 。
(30 分) 无附加限制条件。

题解

1 篇题解

登录后即可使用 Markdown 发布题解。

YuyiLv.6👑 站长管理员

P13512 [KOI 2025 1] 稻草人题解 Author: Yuyi 题意分析题目的核心在于：一支初始力量为 $P$ 的箭，每穿过一个防御力为 $A k$ 的稻草人，力量减少 $A k$（如果 $P \le A k$ 则直接停止）。这等价于：要使箭停止，沿途经过并生效的稻草人防御力之和必须大于等于 $P$。对于每个位置 $i$，目标是从前 $i…

点击展开完整题解点击收起题解

2026年8月9日 22:36

P13512 [KOI 2025 #1] 稻草人题解

Author: Yuyi

题意分析

题目的核心在于：一支初始力量为 $P$ 的箭，每穿过一个防御力为 $A_k$ 的稻草人，力量减少 $A_k$ （如果 $P \le A_k$ 则直接停止）。这等价于：要使箭停止，沿途经过并生效的稻草人防御力之和必须大于等于 $P$ 。对于每个位置 $i$ ，目标是从前 $i$ 个稻草人中，挑选出最少数量的稻草人，使得它们的防御力总和 $\ge P$ 。如果全选都无法达到 $P$ ，则输出 $-1$ 。

部分分解法与暴力代码

对于 $N \le 5000$ 的部分分（Subtask 1, 2）：在每个位置 $i$ ，可以将前 $i$ 个数拷贝出来并降序排序，然后从大到小贪心累加，直到和 $\ge P$ 为止。此时累加的个数就是答案。如果所有数加起来都 $< P$ ，则说明无解，输出 $-1$ 。单次查询需要 $O(i \log i)$ 的时间，总时间复杂度为 $O(N^2 \log N)$ ，足以拿到对应的部分分。

// 暴力部分分代码 O(N^2 log N)
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 5e5+5;
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int n;
ll p;
ll a[maxn];
void solve()
{
    read(n),read(p);
    rep(i,1,n) read(a[i]);
    rep(i,1,n)
    {
        vector<ll> temp;
        ll total_sum = 0;
        rep(j,1,i)
        {
            temp.push_back(a[j]);
            total_sum += a[j];
        }
        if(total_sum < p) cout << -1 << " ";
        else
        {
            sort(temp.begin(),temp.end(),greater<ll>());
            ll cur_sum = 0;
            int count = 0;
            for(ll x : temp)
            {
                cur_sum += x;
                count++;
                if(cur_sum >= p) break;
            }
            cout << count << " ";
        }
    }
    cout << endl;
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T);
    while(T--) solve();
    return 0;
}

正解推导过程

在暴力的过程中可以发现：每次都在重复“排序”并“取最大的几个数”这一操作。如果当前已经选出了一组数量最小的稻草人，当遇到一个新的稻草人 $A_i$ 时，应该如何快速更新策略？

显然，为了用最少的稻草人凑够力量 $P$ ，应该始终优先使用防御力最大的那些稻草人。因此，可以使用一个**小根堆（优先队列）**来动态维护“当前被选中的最优稻草人集合”。

具体做法如下：

当遍历到第 $i$ 个稻草人时，无脑将其加入集合（入堆），并把它的防御力加到集合总和 sum 中。此时由于加入了新元素，集合总和可能会大于 $P$ 甚至盈余很多。
为了使选用的稻草人数量最少，可以尝试从集合中剔除防御力最小的稻草人。
检查堆顶元素（当前集合中的最小值）：如果剔除掉它之后，剩下的稻草人总和仍然 $\ge P$ ，那么就可以放心地将其剔除（出堆），从而成功减少使用的稻草人数量。
反复执行这个剔除操作，直到去掉堆顶元素会导致总和 $< P$ 为止。此时堆里保留的，就是能凑出 $\ge P$ 的数量最少的最大元素集合。堆内元素的个数，也就是当前的最优答案。

正解代码及分析

以下是基于上述贪心+优先队列思路的代码实现：

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 5e5+5;
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int n;
ll p;
// 使用小根堆维护当前选择的稻草人防御力集合
priority_queue<ll,vector<ll>,greater<ll>> pq;
void solve()
{
    read(n),read(p);
    ll sum = 0; // 记录堆内稻草人的防御力总和
    rep(i,1,n)
    {
        ll a;
        read(a);
        
        // 新来的稻草人无脑入堆
        pq.push(a);
        sum += a;
        
        // 贪心剔除：如果去掉堆里最小的稻草人后，总和依然 >= p，则大胆去掉它
        while(!pq.empty() && sum-pq.top() >= p)
        {
            sum -= pq.top();
            pq.pop();
        }
        
        // 如果把所有出现的稻草人都加上，总和依然 < p，说明无解
        if(sum < p) cout << -1 << " "; 
        // 否则，经过剔除后堆内剩余的稻草人数量即为最少数量
        else cout << pq.size() << " ";
    }
    cout << endl;
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T);
    while(T--) solve();
    return 0;
}

复杂度分析

时间复杂度：每个稻草人的防御力最多入堆一次、出堆一次。对于 $N$ 个稻草人，优先队列的单次插入和弹出操作复杂度均为 $O(\log N)$ 。因此总时间复杂度为 $O(N \log N)$ 。对于 $N \le 500,000$ 的数据规模可以非常轻松地通过。
空间复杂度：需要一个优先队列来存储稻草人的防御力，最坏情况下所有稻草人都入堆且不出堆（即总和始终 $< P$ ），空间复杂度为 $O(N)$ 。

Generated by Gemini 3.1 Pro

讨论

0 条讨论

登录后即可使用 Markdown 发起讨论和回复。

还没有讨论，来发起第一条吧。