why100 @ 2024-10-02 16:29:29

#include<iostream>
#include<cstdio>
#include<algorithm> 
using namespace std;
int n,m,s,l[200010],r[200010],cnt[200010],w[200010];
long long sum[200010];
pair<int,int>a[200010];
void pre(int W)
{
    sum[0] = cnt[0] = 0;
    if(a[0].first >= W)
    {
        sum[0] = a[0].second;
        cnt[0]++;
    }
    for(int i = 1;i < n;i++)
    {
        sum[i] = sum[i-1];
        cnt[i] = cnt[i-1];
        if(a[i].first >= W)
        {
            sum[i] += a[i].second;
            cnt[i]++;
        }
    }
}
long long cn(int W)
{
    long long su = 0;
    pre(W);//打前缀表
    for(int i = 0;i < n;i++)
    {
        su += (cnt[r[i]]-cnt[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
    }
    return su;
}
void PR()
{
    for(int i = 0;i < n;i++)

    {
//      printf("%d ",sum[i]);
    }
//  cout << endl;
}
int main()
{
    scanf("%d %d %d",&n,&m,&s);
    for(int i = 0;i < n;i++)
    {
        scanf("%d %d",&a[i].first,&a[i].second);
        //w[i] = a[i].first;
    }
    for(int i = 0;i < m;i++)
    {
        scanf("%d %d",&l[i],&r[i]);
        l[i]--,r[i]--;
    }
    //sort(w,w+n);
    int l = 0,r = 1E6;
    long long anx = 0x3f3f3f3f3f3f3f3,anm = -0x3f;
    while(l <= r)
    {
        int m = (l+r)>>1;//二分W
        long long t = cn(m);//求分
        //PR();
        if(t > s)
        {
            l = m+1;
            anx = min(t,anx);
        }
        else if(t == s)
        {
            anm=anx=s;
            break;
         } 
        else
        {
            anm = max(anm,t);
            r = m-1;
        }
    }
    long long ans;
    if((s-anm) > (anx-s))
    {
        ans = anx-s;
    }
    else
    {
        ans = s-anm;
    }
    cout <<ans;
    return 0;
}

by zyq777 @ 2024-10-08 22:29:57

看不懂你写的一大堆，感觉没思路提供一下我的代码（勿抄）
![]()```c

include<bits/stdc++.h>

define ll long long

define R register int

define I return

define LOVE 0

define LUOGU ;

pragma GCC optimize(3)

using namespace std;

ll n, m, s, l = 0, r, mid, ans;
ll w[200010], v[200010], le[200010], ri[200010], ss;
ll Min = 1e15;
ll q[200010], p[200010];

int main() {
scanf("%lld%lld%lld", &n, &m, &s);
for(R i = 1; i <= n; i++) {
scanf("%lld%lld", &w[i], &v[i]);
r = max(r, w[i]);
}
for(R i = 1; i <= m; i++) { scanf("%lld%lld", &le[i], &ri[i]);
}

while(l <= r) {   
    ans = 0, mid = (l + r) >> 1;  
    for(R i = 1; i <= n; i++) {    
        if(w[i] > mid) {  
            q[i] = q[i - 1] + 1;  
            p[i] = p[i - 1] + v[i];  
        } else {  
            q[i] = q[i - 1];  
            p[i] = p[i - 1];  
        }  
    }  

    for(R i = 1; i <= m; i++) { 
        ans += (q[ri[i]] - q[le[i] - 1]) * (p[ri[i]] - p[le[i] - 1]);  
    }  
    ss = s - ans;   
    if(ss < 0) l = mid + 1;
    else r = mid - 1;  

    Min = min(Min, abs(ss));  
}  
printf("%lld", Min);   
return 0;   

}

希望能给你提供思路(:

by zyq777 @ 2024-10-08 22:30:32

#include<bits/stdc++.h>  
#define ll long long  
#define R register int  
#define I return   
#define LOVE 0  
#define LUOGU ;  
#pragma GCC optimize(3) 
using namespace std;  

ll n, m, s, l = 0, r, mid, ans;  
ll w[200010], v[200010], le[200010], ri[200010], ss;  
ll Min = 1e15;     
ll q[200010], p[200010];   

int main() {  
    scanf("%lld%lld%lld", &n, &m, &s);  
    for(R i = 1; i <= n; i++) {  
        scanf("%lld%lld", &w[i], &v[i]);  
        r = max(r, w[i]);  
    }  
    for(R i = 1; i <= m; i++) { 
        scanf("%lld%lld", &le[i], &ri[i]);  
    }  

    while(l <= r) {   
        ans = 0, mid = (l + r) >> 1;  
        for(R i = 1; i <= n; i++) {    
            if(w[i] > mid) {  
                q[i] = q[i - 1] + 1;  
                p[i] = p[i - 1] + v[i];  
            } else {  
                q[i] = q[i - 1];  
                p[i] = p[i - 1];  
            }  
        }  

        for(R i = 1; i <= m; i++) { 
            ans += (q[ri[i]] - q[le[i] - 1]) * (p[ri[i]] - p[le[i] - 1]);  
        }  
        ss = s - ans;   
        if(ss < 0) l = mid + 1;
        else r = mid - 1;  

        Min = min(Min, abs(ss));  
    }  
    printf("%lld", Min);   
    return 0;   
} 

by zyq777 @ 2024-10-08 22:31:36

@why100

by zyq777 @ 2024-10-08 22:33:05

抱歉，不一定对

by zyq777 @ 2024-10-08 22:33:55

#include<bits/stdc++.h>  
#define ll long long  
#define R register int  
#define I return   
#define LOVE 0  
#define LUOGU ;  
#pragma GCC optimize(3) // O3 optimization  
using namespace std;  

ll n, m, s, l = 0, r, mid, ans; //朴素定义  
ll w[200010], v[200010], le[200010], ri[200010], ss;  
ll Min = 1e15;   // 记录结果   
ll q[200010], p[200010];  // 前缀和记录  

int main() {  
    scanf("%lld%lld%lld", &n, &m, &s);  
    for(R i = 1; i <= n; i++) {  
        scanf("%lld%lld", &w[i], &v[i]);  
        r = max(r, w[i]);  // 右边界设为最大的w[i]  
    }  
    for(R i = 1; i <= m; i++) { // 读入m个区间   
        scanf("%lld%lld", &le[i], &ri[i]);  
    }  

    while(l <= r) { // 二分查找  
        ans = 0, mid = (l + r) >> 1;  
        for(R i = 1; i <= n; i++) { // 更新前缀和数组   
            if(w[i] > mid) {  
                q[i] = q[i - 1] + 1;  
                p[i] = p[i - 1] + v[i];  
            } else {  
                q[i] = q[i - 1];  
                p[i] = p[i - 1];  
            }  
        }  

        for(R i = 1; i <= m; i++) { // 计算Y的总和   
            ans += (q[ri[i]] - q[le[i] - 1]) * (p[ri[i]] - p[le[i] - 1]);  
        }  
        ss = s - ans; // 计算当前差值  
        if(ss < 0) l = mid + 1; // 如果小于0，增大min weight  
        else r = mid - 1; // 否则缩小r的值   

        Min = min(Min, abs(ss)); // 更新最小值   
    }  
    printf("%lld", Min); // 输出结果   
    return 0;   
} 

by why100 @ 2024-10-12 18:04:14

@zyq777 谢谢大佬啦