lyc54088 @ 2024-12-25 21:54:56

#include<iostream>
#include<algorithm>
using namespace std;
    typedef long long ll;
    struct str{
        ll w,v;
    }a[200005];
    bool cmp(str x,str y){
        return x.w<y.w;
    }
    ll n,m,s,l[200005],r[200005],pre[200005],ans=1e18;
    ll Find(ll x,ll L,ll R){
        ll l=L,r=R,Ans=-1;
        while(l<=r){
            ll mid=(l+r)>>1;
            if(a[mid].w<x){
                l=mid+1;
            }else{
                Ans=mid;
                r=mid-1;
            }
        }
        if(Ans==-1) return -1;
        return Ans+L-1;
    }                             //自己写的upper_bound
    ll check(ll W){
        ll sum=0;
        for(int i=1;i<=m;i++){
            ll idx=Find(W,l[i],r[i]);
            if(idx==-1) continue; 
            sum+=(n-idx+1)*(pre[n]-pre[idx-1]); 
        }
        return sum;
    }
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].v;
    for(int i=1;i<=m;i++) cin>>l[i]>>r[i];
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i].v;
    ll L=0,R=a[n].w+1; 
    while(L<=R){
        ll mid=(L+R)>>1;
        ll x=check(mid);
        if(x>s){
            ans=min(x-s,ans);
            L=mid+1;
        }else if(x==s){
            cout<<0;
            return 0;
        }else{
            ans=min(ans,s-x);
            R=mid-1;
        }
    }
    cout<<ans;
    return 0;
}

by guozheyu2024 @ 2024-12-25 22:47:46

哪 一题 ？

by guozheyu2024 @ 2024-12-25 22:50:37

include<bits/stdc++.h>

using namespace std; const int maxn=200010; int w[maxn],v[maxn],l[maxn],r[maxn]; long long pre_n[m

#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
int w[maxn],v[maxn],l[maxn],r[maxn];
long long pre_n[maxn],pre_v[maxn];
long long Y,s,sum;
int n,m,mx=-1,mn=2147483647;
bool check(int W)
{   
    Y=0,sum=0;
    memset(pre_n,0,sizeof(pre_n));
    memset(pre_v,0,sizeof(pre_v));
    for(int i=1;i<=n;i++)
    {
        if(w[i]>=W) pre_n[i]=pre_n[i-1]+1,pre_v[i]=pre_v[i-1]+v[i];
        else pre_n[i]=pre_n[i-1],pre_v[i]=pre_v[i-1];
    }
    for(int i=1;i<=m;i++)
        Y+=(pre_n[r[i]]-pre_n[l[i]-1])*(pre_v[r[i]]-pre_v[l[i]-1]);

    sum=llabs(Y-s);
    if(Y>s) return true;
    else return false;

}
int main(){
//  freopen("qc.in","r",stdin);
//  freopen("qc.out","w",stdout); 
    scanf("%d %d %lld",&n,&m,&s); 
    for(int i=1;i<=n;i++)
    {
        scanf(" %d %d",&w[i],&v[i]);
        mx=max(mx,w[i]);
        mn=min(mn,w[i]);    
    }
    for(int i=1;i<=m;i++)
        scanf(" %d %d",&l[i],&r[i]);
    int left=mn-1,right=mx+2,mid;  //这里有的人说要特判左右端点的check，但是其实你把left开成mn-1,right开成mx+2(注意取mx+1时即为W比所有都大，Y是0，这个情况要考虑，所以+2包含mx+1)就可以包含左右端点的check了，会简单点。
    long long ans=0x3f3f3f3f3f3f3f3f;//ll 范围内的无穷大，近似于(maxll/2)的大小
    while(left<=right)
    {
        mid=(left+right)>>1;
        if(check(mid))  left=mid+1;
        else right=mid-1;
        if(sum<ans) ans=sum;
    }
    printf("%lld",ans);
    return 0;
}

axn],pre_v[maxn]; long long Y,s,sum; int n,m,mx=-1,mn=2147483647; bool check(int W) {
Y=0,sum=0; memset(pre_n,0,sizeof(pre_n)); memset(pre_v,0,sizeof(pre_v)); for(int i=1;i<=n;i++) { if(w[i]>=W) pre_n[i]=pre_n[i-1]+1,pre_v[i]=pre_v[i-1]+v[i]; else pre_n[i]=pre_n[i-1],pre_v[i]=pre_v[i-1]; } for(int i=1;i<=m;i++) Y+=(pre_n[r[i]]-pre_n[l[i]-1])*(pre_v[r[i]]-pre_v[l[i]-1]);

sum=llabs(Y-s);
if(Y>s) return true;
else return false;

} int main(){ // freopen("qc.in","r",stdin); // freopen("qc.out","w",stdout); scanf("%d %d %lld",&n,&m,&s); for(int i=1;i<=n;i++) { scanf(" %d %d",&w[i],&v[i]); mx=max(mx,w[i]); mn=min(mn,w[i]);
} for(int i=1;i<=m;i++) scanf(" %d %d",&l[i],&r[i]); int left=mn-1,right=mx+2,mid; //这里有的人说要特判左右端点的check，但是其实你把left开成mn-1,right开成mx+2(注意取mx+1时即为W比所有都大，Y是0，这个情况要考虑，所以+2包含mx+1)就可以包含左右端点的check了，会简单点。 long long ans=0x3f3f3f3f3f3f3f3f;//ll 范围内的无穷大，近似于(maxll/2)的大小 while(left<=right) { mid=(left+right)>>1; if(check(mid)) left=mid+1; else right=mid-1; if(sum<ans) ans=sum; } printf("%lld",ans); return 0; }