⚡CodeY OJ
登录注册
P13514

[KOI 2025 #1] 干草堆

提高+/省选−

题目背景

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

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

题目描述

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

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

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

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

输入格式

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

第二行给定可以在位置 ii (1≤i≤N1 \le i \le N) 放置的干草堆的防御力 D1,D2,⋯ ,DND_1, D_2, \cdots, D_N，以空格分隔。

从第三行开始的 QQ 行，给出 QQ 个整数对。其中第 jj (1≤j≤Q1 \le j \le Q) 行给定 XjX_j 和 PjP_j，以空格分隔。

输出格式

输出 QQ 行。其中第 jj (1≤j≤Q1 \le j \le Q) 行输出 f(Xj,Pj)f(X_j, P_j) 的值。

输入输出样例

输入样例 #1

text
5 6
2 5 6 1 12
1 1
5 14
2 8
3 7
4 14
5 1

输出样例 #1

text
1
2
-1
2
4
1

输入样例 #2

text
5 5
3 6 1 1 10
1 10
2 10
3 10
4 10
5 10

输出样例 #2

text
-1
-1
3
3
1

说明/提示

限制条件

  • 给定的所有数都是整数。
  • 1≤N,Q≤300,0001 \le N, Q \le 300,000
  • 对于每个 1≤i≤N1 \le i \le N 的 ii，都有 1≤Di≤1091 \le D_i \le 10^9。
  • 对于每个 1≤j≤Q1 \le j \le Q 的 jj，都有 1≤Xj≤N1 \le X_j \le N。
  • 对于每个 1≤j≤Q1 \le j \le Q 的 jj，都有 1≤Pj≤1091 \le P_j \le 10^9。

子任务

  1. (6 分) N,Q≤18N, Q \le 18。
  2. (16 分) N,Q≤5000N, Q \le 5000。
  3. (18 分) 对于所有 1≤i≤N1 \le i \le N 的 ii，Di≤300D_i \le 300。
  4. (32 分) 对于所有 1≤i<N1 \le i < N 的 ii，Di≤Di+1D_i \le D_{i+1}。
  5. (28 分) N=QN=Q，且对于所有 1≤j≤Q1 \le j \le Q 的 jj，Xj=jX_j=j，且 P1=P2=⋯=PQP_1 = P_2 = \cdots = P_Q。
  6. (16 分) 对于所有 1≤j≤Q1 \le j \le Q 的 jj，Xj=NX_j = N。
  7. (12 分) 对于所有 1≤i<j≤N1 \le i < j \le N 的 i,ji, j，Di≠DjD_i \ne D_j。
  8. (22 分) 无附加限制条件。

🚀 提交评测

登录并绑定洛谷账号后即可在此在线提交代码并实时评测。

前往登录

💡 题解 (1)

登录后即可撰写并分享您的解题思路。
YuyiLv.142👑 站长管理员
2026年8月10日 13:37

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

Author: Yuyi

题意分析

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

部分分解法与暴力代码

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

cpp
// 暴力部分分代码 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≤300,000N, Q \le 300,000 的数据规模，为了避免使用巨大内存的主席树，我们可以采用离线查询 + 普通权值线段树的超强思路：

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

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

离线正解代码及分析

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

💬 题目讨论 (0)

登录后可以发起或参与讨论。

暂无讨论内容。

📊 题目信息

题号P13514
难度提高+/省选−
时间限制2000 ms
内存限制1024 MB
题目来源洛谷题库
算法标签
线段树二分树状数组前缀和离线处理

⚡ 快速操作

在线提交代码在洛谷打开原题 ↗