题解 | #小红打怪#

思路看注释

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
struct node {
    int x, y, z;
}nod[N];
int n, h, k, arr[N], cnt, sum;
int sm[N];

signed main(void)
{
    cin >> n >> h >> k;
    for (int i = 1; i < N; i++)//打表，存一下在下标时间内可造成的伤害
    {
        sum++;
        if ((i - 1) % 3 == 0)sum++;
        arr[++cnt] = sum;
    }

    for (int i = 1; i <= n; i++)
    {
        cin >> nod[i].x >> nod[i].y;
        nod[i].z = ((lower_bound(arr + 1, arr + 1 + cnt, nod[i].x))-arr - 1) * nod[i].y;//二分查表，存一下消灭怪会对自己造成的伤害
    }
    sort(nod + 1, nod + 1 + n, [](node a, node b) {return a.z < b.z; });//给怪排伤害个序

    for (int i = 1; i <= n; i++)//前缀和存入消灭下标个怪会对自己造成的伤害
    {
        sm[i] = sm[i - 1] + nod[i].z;
    }

    int q;
    cin >> q;
    while (q--)
    {
        int hp; cin >> hp;
        hp = hp * k + h;
        int ans = lower_bound(sm + 1, sm + 1 + n, hp) - sm - 1;//二分查找HP生命时可打死多少怪
        cout << ans << ' ';
    }
    return 0;
}

附上python题解

from bisect import *
N = 100005
n,h,k=map(int,input().split())
arr=[]
harm=[]
ans=[]
Sm=[ int(0x3f3f3f3f3f3f3f3f) for _ in range(N)]

sm=0
for i in range(N):
    if i%3==0:
        sm+=1
    sm+=1
    arr.append(sm)

for i in range(n):
    x,y=map(int,input().split())
    harm.append((bisect_left(arr,x))*y)
harm.sort()

Sm[0]=harm[0]
for i in range(1,n):
    Sm[i]=Sm[i-1]+harm[i]

q=int(input())
for i in list(map(int,input().split())):
    hp=h+k*i
    ans.append(bisect_left(Sm,hp)) 
for i in ans:
    print(i,end=' ')