最暴力解法$O(VMN)$,25pts

枚举每个可能的$m$,然后依次计算每个$Y_i$,得到最小值

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200010;
int n,m;
LL S;
int w[N],v[N];
int l[N],r[N];
int main()
{
    cin>>n>>m>>S;
    int maxv=0;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
        maxv=max(maxv,w[i]);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>l[i]>>r[i];
    }
    LL res=1e12;
    for(int i=1;i<=maxv;i++)
    {
        LL ysum=0;
        
        for(int j=1;j<=m;j++)
        {
            LL cnt=0,sum=0;
            for(int k=l[j];k<=r[j];k++)
            {
                if(w[k]>=i)
                {
                    cnt++,sum+=v[k];
                }
            }
            ysum+=cnt*sum;
        }
        res=min(res,abs(ysum-S));
    }
    cout<<res;
    return 0;
}

前缀和优化(MN),60pts

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200010;
int n,m;
LL S;
int w[N],v[N];
int l[N],r[N];
int cnt[N];
LL sum[N];
LL get(int W) //获取选取W的检验值
{
    for(int i=1;i<=n;i++)
    {
        if(w[i]>=W)
        {
            sum[i]=sum[i-1]+v[i];
            cnt[i]=cnt[i-1]+1;
        }
        else
        {
            sum[i]=sum[i-1];
            cnt[i]=cnt[i-1];
        }
    }
    LL res=0;
    for(int i=1;i<=m;i++)
    {
        res=res+(cnt[r[i]]-cnt[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
    }
    return res;
}
int main()
{
    cin>>n>>m>>S;
    int maxv=0;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
        maxv=max(maxv,w[i]);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>l[i]>>r[i];
    }
    LL res=1e12;
    for(int i=0;i<=maxv;i++)
    {
        res=min(res,abs(get(i)-S));
    }
    cout<<res;
    return 0;
}

观察每个区间的值 : $$ y_i=\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_j$$ 当 $W$ 增大时，区间$[L_i,R_i]$;中满足要求的$(w_i,v_i)$会減少，同时所有$v_i≥ 0$，因此 $Y_i$的值也会减少。由于 $Y=\sum Y_i$，所以 $Y$随 $W$ 单调递减。

因此我们可以二分出距离 $S$ 最近的值。

剩下的问题是当 $W$ 确定之后，我们如何快速求出每个 $Y_i$。这里可以预处理出所有满足 $w_i> W$ 的元素的前缀和，之后可以 0(1)时间求出每个区间中所有 $v_i$ 的和以及满足要求的元素个数。

时间复杂度分析

总共二分 $O(logW)$次，每次预处理前缀和的计算量是 $O(N)$，求$Y$的计算量是 $O(M)$。

因此总时间复杂度是 $O(N+M)logW)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200010;
int n,m;
LL S;
int w[N],v[N];
int l[N],r[N];
int cnt[N];
LL sum[N];
LL get(int W) //获取选取W的检验值
{
    for(int i=1;i<=n;i++)
    {
        if(w[i]>=W)
        {
            sum[i]=sum[i-1]+v[i];
            cnt[i]=cnt[i-1]+1;
        }
        else
        {
            sum[i]=sum[i-1];
            cnt[i]=cnt[i-1];
        }
    }
    LL res=0;
    for(int i=1;i<=m;i++)
    {
        res=res+(cnt[r[i]]-cnt[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
    }
    return res;
}
int main()
{
    cin>>n>>m>>S;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>l[i]>>r[i];
    }
    int l=0,r=1e6;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(get(mid)>=S) l=mid; //说明y>=S,说明y应该小一些，也就是w需要大一些
        else r=mid-1;
    }
    cout<<min(abs(get(r)-S),abs(S-get(r+1)));
    return 0;
}