题解：P11470 昆明之泪

Night_sea_64 · 2024-12-28 18:06:53 · 题解

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

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

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

这里 \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;
}