題目鏈接:傳送門
題目大意:給你n個物品，每件物品有重量 W 和價值 V，給m個區間，和一個標準值。(n,m最大200000)
要求找到一個值x，使得m個所有區間的權值和與標準值的差的絕對值最小。單個區間權值計算公式(數目num=0，價值sum=0,若滿足 Wi >= x ,則++num，sum+=Vi)
單個區間權值為num*sum
題目思路: 二分+前綴和
??????? ? 首先權值和與X是遞減關系，X越大所得值越小，我們容易想到二分，但是m個區間的比較判斷怎么處理，如果直接模擬，復雜度最大可達 n^2logn 顯然不行
其實我們可以，用前綴和的想法，用一個數組num 表示1~i 滿足W>=x的個數，sum對應為滿足條件的W對應的V之和，那么對于區間我們可直接O（1）得值
每次前綴處理O（n） ，所以總復雜度 nlogn ，還有此題需用long long 不然WA
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include<functional> #include <set> #include <map> #include <climits> #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 200005 #define maxn 10000500 typedef pair<int,int> PII; typedef long long LL;LL n,m; LL k,sta,l=-1,r,ans=1ll<<62; struct Node{LL x,v; }node[N]; struct Seg{LL x,y; }seg[N]; LL num[N],sum[N]; bool match(LL x){for(LL i=1;i<=n;++i){num[i]=num[i-1];sum[i]=sum[i-1];if(node[i].x>=x){++num[i];sum[i]+=node[i].v;}}LL temp=0;for(LL i=1;i<=m;++i){LL t1=seg[i].x,t2=seg[i].y;temp+=(sum[t2]-sum[t1-1])*(num[t2]-num[t1-1]);}temp=temp-sta;ans=min(ans,llabs(temp));return temp>=0; } int main(){LL i,j,v;scanf("%lld%lld%lld",&n,&m,&sta);for(i=1;i<=n;++i){scanf("%lld%lld",&node[i].x,&node[i].v);r=max(r,node[i].x);}for(i=1;i<=m;++i){scanf("%lld%lld",&seg[i].x,&seg[i].y);}++r;while(l<=r){LL mid=l+r>>1;if(match(mid)){l=mid+1;}else r=mid-1;}printf("%lld\n",ans);return 0; }
?
