自动搬运

查看原文

来自洛谷，原作者为

	Night_sea_64 距离省选还有 +inf 天。

搬运于2025-08-24 23:07:39，当前版本为作者最后更新于2024-12-28 18:06:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这题比较简单，但我场上因为来晚+中途离开导致最后没调出来。

基本上看到数据范围就能会这道题了。发现 $x$ 之和很小，所以直接考虑背包，$f(j)$ 为 $x$ 之和为 $j-10^5$，$y$ 之和的最大值。转移一下即可，唯一需要注意的就是 $x$ 的正负需要分类。

然后看那个询问。把式子整体减去 $b$，变成了

$$\min\left(a - b + \sum\limits_{i = 1}^{k} x_{p_i}, \sum\limits_{i = 1}^{k} y_{p_i}\right) $$

这里 $\sum\limits_{i = 1}^{k} y_{p_i}$ 就是 $f\left(\sum\limits_{i = 1}^{k} x_{p_i}\right)$ 的值。考虑二分答案为 $mid$，则 $\sum\limits_{i = 1}^{k} x_{p_i}\ge mid+b-a$，满足这个情况的前提下还要找到至少一个 $\sum\limits_{i = 1}^{k} x_{p_i}$，使得 $f\left(\sum\limits_{i = 1}^{k} x_{p_i}\right)\ge mid$。

这样的话，给 $f$ 数组做一个后缀 max，就可以求出了。

时间复杂度为 $O(nW_x+m\log W_y)$。其中 $W_x=10^5,W_y=10^{12}$。

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
int n,m,x[1010],y[1010];
int f[200010];
bool chk(int a,int b,int k)
{
    if(k+b-a>200000)return 0;
    return f[max(0ll,k+b-a)]>=k;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    memset(f,-999999,sizeof(f));
    f[100000]=100000;
    for(int i=1;i<=n;i++)
    {
        if(x[i]>=0)
        {
            for(int j=200000;j>=x[i];j--)
                f[j]=max(f[j],f[j-x[i]]+y[i]);
        }
        else
        {
            for(int j=0;j<=200000+x[i];j++)
                f[j]=max(f[j],f[j-x[i]]+y[i]);
        }
    }
    for(int i=200000;i>=0;i--)f[i]=max(f[i],f[i+1]);
    cin>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        int l=-1e12,r=200000+a-b,ans=100000-b;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(chk(a,b,mid))l=mid+1,ans=mid;
            else r=mid-1;
        }
        cout<<ans-100000+b<<endl;
    }
    return 0;
}