P13514

[KOI 2025 #1] 干草堆

题目背景

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

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

题目描述

一支带有力量 $P$ 的箭从数轴上的位置 0 向右方发射。在每个整数位置 $i$ ( $1 \le i \le N$ )，最多可以设置一个防御力为 $D_i$ 的干草堆。

当箭撞到干草堆时，如果箭的力量小于或等于该干草堆的防御力，箭会立即停止。反之，如果箭的力量大于防御力，箭的力量会减去 $D_i$ ，然后穿过干草堆继续飞行。

对于两个整数 $X, P$ ，我们将 $f(X, P)$ 的值定义为“为了使力量为 $P$ 的箭在位置 $X$ 或其左侧停止所需要安装的干草堆的最小数量”。如果无论如何安装都无法使箭停止，则定义 $f(X, P) = -1$ 。

请编写一个程序，对于 $Q$ 个整数对 $(X_j, P_j)$ ( $1 \le j \le Q$ )，分别求出 $f(X_j, P_j)$ 的值。

输入格式

第一行给定可以安装干草堆的位置数量 $N$ 和发射的箭的数量 $Q$ ，以空格分隔。

第二行给定可以在位置 $i$ ( $1 \le i \le N$ ) 放置的干草堆的防御力 $D_1, D_2, \cdots, D_N$ ，以空格分隔。

从第三行开始的 $Q$ 行，给出 $Q$ 个整数对。其中第 $j$ ( $1 \le j \le Q$ ) 行给定 $X_j$ 和 $P_j$ ，以空格分隔。

输出格式

输出 $Q$ 行。其中第 $j$ ( $1 \le j \le Q$ ) 行输出 $f(X_j, P_j)$ 的值。

输入输出样例

输入样例 #1

输出样例 #1

输入样例 #2

输出样例 #2

说明/提示

限制条件

给定的所有数都是整数。
$1 \le N, Q \le 300,000$
对于每个 $1 \le i \le N$ 的 $i$ ，都有 $1 \le D_i \le 10^9$ 。
对于每个 $1 \le j \le Q$ 的 $j$ ，都有 $1 \le X_j \le N$ 。
对于每个 $1 \le j \le Q$ 的 $j$ ，都有 $1 \le P_j \le 10^9$ 。

子任务

(6 分) $N, Q \le 18$ 。
(16 分) $N, Q \le 5000$ 。
(18 分) 对于所有 $1 \le i \le N$ 的 $i$ ， $D_i \le 300$ 。
(32 分) 对于所有 $1 \le i < N$ 的 $i$ ， $D_i \le D_{i+1}$ 。
(28 分) $N=Q$ ，且对于所有 $1 \le j \le Q$ 的 $j$ ， $X_j=j$ ，且 $P_1 = P_2 = \cdots = P_Q$ 。
(16 分) 对于所有 $1 \le j \le Q$ 的 $j$ ， $X_j = N$ 。
(12 分) 对于所有 $1 \le i < j \le N$ 的 $i, j$ ， $D_i \ne D_j$ 。
(22 分) 无附加限制条件。

题解

1 篇题解

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

YuyiLv.6👑 站长管理员

P13514 [KOI 2025 1] 干草堆题解 Author: Yuyi 题意分析题目要求我们在前 $X$ 个干草堆中，选出最少数量的干草堆，使得它们的防御力总和大于等于箭的力量 $P$。由于我们的目标是“最小化”干草堆的数量，根据贪心策略，我们显然应该优先选择防御力最大的干草堆。也就是说，对于每次查询 $(X, P)$，其实质就是：把前 $…

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

2026年8月9日 22:37

P13514 [KOI 2025 #1] 干草堆题解

Author: Yuyi

题意分析

题目要求我们在前 $X$ 个干草堆中，选出最少数量的干草堆，使得它们的防御力总和大于等于箭的力量 $P$ 。由于我们的目标是“最小化”干草堆的数量，根据贪心策略，我们显然应该优先选择防御力最大的干草堆。也就是说，对于每次查询 $(X, P)$ ，其实质就是：把前 $X$ 个干草堆的防御力降序排序，然后从大到小累加，直到和 $\ge P$ 为止，此时累加的个数就是答案。如果前 $X$ 个干草堆的防御力总和 $< P$ ，说明无论全选也无法让箭停下，输出 $-1$ 。

部分分解法与暴力代码

对于 $N, Q \le 5000$ 的部分分：我们可以对每一次查询，把前 $X$ 个干草堆的防御力提取出来放入 vector 中。将其降序排序后，从大到小累加并计数。单次查询的时间复杂度为 $O(X \log X)$ ，总体时间复杂度为 $O(Q \cdot N \log N)$ ，可以通过对应的数据点。

// 暴力部分分代码 O(Q * N 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 = 5005; //必须根据题目约束动态调整
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,q;
ll a[maxn];
void solve()
{
    read(n),read(q);
    rep(i,1,n) read(a[i]);
    rep(i,1,q)
    {
        int x;
        ll p;
        read(x),read(p);
        vector<ll> vec;
        ll tot = 0;
        rep(j,1,x)
        {
            vec.push_back(a[j]);
            tot += a[j];
        }
        if(tot < p)
        {
            cout << -1 << endl;
            continue;
        }
        sort(vec.begin(),vec.end(),greater<ll>());
        ll cur = 0;
        int ans = 0;
        for(auto v : vec)
        {
            cur += v;
            ans++;
            if(cur >= p) break;
        }
        cout << ans << 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, Q \le 300,000$ 的数据规模，为了避免使用巨大内存的主席树，我们可以采用离线查询 + 普通权值线段树的超强思路：

离线与排序：我们将所有的询问一次性读取进来，记录下它们原本的编号 id，然后将这些询问按照查询的范围 $X$ 进行从小到大排序。
动态插入：由于查询范围 $X$ 变成了单调递增的，我们可以维护一棵全局的、以“干草堆防御力大小”为值域的权值线段树。设置一个指针 cur 遍历数组 $A[]$ ，每次遇到一个新的询问的 $X$ ，我们就把指针 cur 移动到 $X$ 的位置，并把沿途新路过的干草堆防御力全部单点插入到线段树里。
线段树查询：每次把干草堆更新到当前 $X$ $X$ 后，我们就直接在当前这棵普通的权值线段树中查询力量 $P$ $P$ 。
- 同样贪心选最大的，优先看右子树（更大的值域）。
- 如果右子树防御力总和 rsum >= P，深入右子树找。
- 如果 rsum < P，把右子树的数量全加上，拿力量 $P$ 减去 rsum，深入左子树凑剩下的力量。
- 到达叶子节点 l（即离散化数组中的具体防御力数值 b[l]）时，向上取整求个数。
离线还原：由于打乱了询问顺序，我们把查询得到的答案存入 ans[id]，最后按原顺序输出即可。

这种离线处理的手法直接将麻烦的主席树降维成了普通的线段树，常数和内存双双得到恐怖级别的优化！

离线正解代码及分析

#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 = 300005; //必须根据题目约束动态调整
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,q;
ll a[maxn],b[maxn];
struct Query
{
    int x;
    ll p;
    int id;
}Q[maxn];
bool cmp(Query A,Query B)
{
    return A.x < B.x;
}
int ans[maxn];
int cnt[maxn*4]; //普通线段树仅需4倍空间
ll sum[maxn*4];
void add(int p,int l,int r,int x,ll d)
{
    if(l == r)
    {
        cnt[p]++;
        sum[p] += d;
        return;
    }
    int mid = (l+r)>>1;
    if(x <= mid) add(p*2,l,mid,x,d);
    else add(p*2+1,mid+1,r,x,d);
    cnt[p] = cnt[p*2]+cnt[p*2+1];
    sum[p] = sum[p*2]+sum[p*2+1];
}
int query(int p,int l,int r,ll v)
{
    if(l == r) return (v+b[l]-1)/b[l]; //叶子节点所需个数直接向上取整
    int mid = (l+r)/2;
    ll rsum = sum[p*2+1];
    if(v <= rsum) return query(p*2+1,mid+1,r,v);
    return cnt[p*2+1]+query(p*2,l,mid,v-rsum);
}
void solve()
{
    read(n),read(q);
    rep(i,1,n)
    {
        read(a[i]);
        b[i] = a[i];
    }
    sort(b+1,b+1+n);
    int m = unique(b+1,b+1+n)-b-1;
    rep(i,1,q)
    {
        read(Q[i].x),read(Q[i].p);
        Q[i].id = i;
    }
    sort(Q+1,Q+1+q,cmp);
    int cur = 1;
    rep(i,1,q)
    {
        while(cur <= Q[i].x)
        {
            int pos = lower_bound(b+1,b+1+m,a[cur])-b;
            add(1,1,m,pos,a[cur]);
            cur++;
        }
        if(sum[1] < Q[i].p) ans[Q[i].id] = -1;
        else ans[Q[i].id] = query(1,1,m,Q[i].p);
    }
    rep(i,1,q) cout << ans[i] << endl;
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T);
    while(T--) solve();
    return 0;
}

复杂度分析

时间复杂度：排序所有查询需要 $O(Q \log Q)$ ，干草堆离散化耗时 $O(N \log N)$ ；随后指针 cur 从 $1$ 扫到 $N$ ，每个元素只在线段树中插入一次，总插入耗时 $O(N \log N)$ ；每一次查询同样深入 $\log N$ 层的线段树，总查询耗时 $O(Q \log N)$ 。综合总体时间复杂度为 $O((N+Q)\log (N+Q))$ ，极其迅速。
空间复杂度：因为直接抛弃了可持久化做法，我们只需要一棵对应离散化后 $N$ 个不同值域的普通权值线段树。线段树数组仅需开辟 $4$ 倍的 maxn 大小，空间复杂度被完美压缩到了 $O(N)$ ，且查询结构体所需空间也仅是 $O(Q)$ ，没有任何爆内存的风险。

讨论

0 条讨论

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

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