题解：【NOIP2024模拟测试 #30】法国（france）

· · 题解

这题看着不简单，但实际上我们有非常简单的方法解决。

首先，我们会想到暴力，对于每一个国王塔，一个一个卡牌向下加，看看到哪里能使得造成的伤害超过国王塔血量。

不难发现一个结论，就是国王塔升级后，用掉的卡牌不可能变少。因为国王塔升级后，血量和攻击力都不会减小，所以每张卡牌造成的贡献不可能变多。

那么我们容易想到，我们可以记录上一次需要的卡牌，认为这些卡牌是必须要用的卡牌，然后往后找，尝试获得新的贡献，这样，只用循环一遍就可以完成。

但是呢，我们要怎么快速得到已经用掉的卡牌能做出多少贡献呢？

首先，对于每一个国王塔的攻击力，我们可以按照几次攻击能消灭卡牌，把卡牌的血量划分成不同的区间。如果国王塔的攻击力与上一次相同，我们就直接用上一次的区间，否则我们就重新求一次。这样，最多只会查询 4129761 个区间，非常小。

为什么要这么做？因为我们不关心具体卡牌的血量是多少，只关心他们的比值。

容易发现，每张卡牌能做出的贡献只和国王塔当前的攻击力与卡牌的血量的比值相关，而由于我们根据血量划分区间，所以我们可以用树状数组维护一个桶。这个桶以血量作为下标，以这个血量的卡牌总共有多大的攻击力为值，这样，我们就能快速求出一个血量区间内有多少攻击力，而这个血量区间可以攻击的次数是固定的，所以我们将攻击力乘上次数，就是这个区间能做出的贡献，查询复杂度 O(\log n) ，也就是 19 左右。

这样，只需要 19 * 2 * 4129761=156930918 次运算就可以了，时限开了 2s，足够了。

#include<bits/stdc++.h>
using namespace std;
long long n,m,v,a[300010],h[300010],A[300010],H[300010];
long long p[300010];
void add(long long x,long long t)
{
    while(x<=v)
    {
        p[x] += t;
        x += x&-x;
    }
}
long long query(long long x)
{
    long long s=0;
    while(x)
    {
        s += p[x];
        x -= x&-x;
    }
    return s;
}
int main()
{
    freopen("france.in","r",stdin);
    freopen("france.out","w",stdout);

    scanf("%lld%lld%lld",&n,&m,&v);

    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i],&h[i]);
    for(int i=1;i<=m;i++)
        scanf("%lld%lld",&A[i],&H[i]);

    long long j=1,s;
    for(int i=1;i<=m;i++)
    {
        if(A[i]!=A[i-1])
        {
            s=0;
            for(int k=1 ; (k-1)*A[i]<=v ; k++)
                s += (query(min(v, k*A[i])) - query( (k-1)*A[i] ))*k;
        }
        if(s>=H[i])
        {
            printf("%d \n",j-1);
            continue;
        }
        while(j<=n)
        {
            s += ceil(1.0*h[j]/A[i])*a[j];
            add(h[j], a[j]);
            j++;
            if(s>=H[i])
                break;
        }

        if(s<H[i])
        {
            puts("-1");
            continue;
        }
        printf("%d \n",j-1);
    }
    return 0;
}