题解 P1314 【聪明的质监员】

xzyxzy

2017-09-09 11:52:49

Solution

看到这题,哇,那么多区间,肯定是莫队是吧。。/好吧可能只有我是这么想的/ 然后哇,大于w的所有数的一些和,线段树对吧。。/好吧只有我是这么想的/ 然后洋洋洒洒上百行,,写挂了 于是想到了前缀和 于是莫队+前缀和+卡常+玄学剪枝(最优性)AC 不知道莫队的童鞋看下我对题意的解释吧 题目的式子表示的是在区间[l,r]内的所有j,只要w[j]>W,那么就前面的sigma++,后面的sigma+=v[j] 这样就懂了吧,区间内所有符合条件的产品,求其数量乘上价值和 最后所有区间相加即可 我呢也看了很久,最后想出来了,这样的“好题”最锻(chao)炼(ji)思(keng)维(bi)了 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #define ll long long using namespace std; inline ll read() { register char ch=getchar(); register ll h=0; while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();} return h; } ll n,m,s; ll ans=1000000000000000; ll v[200001],w[200001]; ll sqrtn; ll jzh,slh;//价值和,数量和 struct qj{ ll l,r; }a[200001]; inline int cmp(const qj&a,const qj&b)//分块 { if(a.l/sqrtn<b.l/sqrtn)return 1; if(a.l/sqrtn>b.l/sqrtn)return 0; return a.r<b.r; } inline void go_r(ll W,ll x,ll y) { if(x==y)return; if(x>y) { for(register ll i=x;i>=y+1;i--) if(w[i]>=W){slh--;jzh-=v[i];} } else { for(register ll i=x+1;i<=y;i++) if(w[i]>=W){slh++;jzh+=v[i];} } } inline void go_l(ll W,ll x,ll y) { if(x==y)return; if(x>y) { for(register ll i=x-1;i>=y;i--) if(w[i]>=W){slh++;jzh+=v[i];} } else { for(register ll i=x;i<=y-1;i++) if(w[i]>=W){slh--;jzh-=v[i];} } } inline ll check(ll k)//以k为标准 { a[0].l=1;a[0].r=0; slh=0;jzh=0; register ll tot=0; for(register ll i=1;i<=m;i++) { go_r(k,a[i-1].r,a[i].r); go_l(k,a[i-1].l,a[i].l); tot+=slh*jzh; if(tot-s>=ans)return s+1;//如果已经超过了s+ans,那么应该下一次搜的时候要把标准放大,使得tot减小 } if(tot>s)ans=ans<(tot-s)?ans:(tot-s); else ans=ans<(s-tot)?ans:(s-tot); return tot; } int main() { n=read();m=read(); s=read();sqrtn=sqrt(n); for(register ll i=1;i<=n;i++) {w[i]=read();v[i]=read();} for(register ll i=1;i<=m;i++) {a[i].l=read();a[i].r=read();} sort(a+1,a+m+1,cmp); register ll lll=1,rr=1000000; while(lll<rr)//mid越大,检验值越小 { register ll mid=(lll+rr)>>1; if(check(mid)<s)rr=mid; else lll=mid+1; } printf("%lld\n",ans); return 0; } ```