题解 P1314 【聪明的质监员】
xzyxzy
2017-09-09 11:52:49
看到这题,哇,那么多区间,肯定是莫队是吧。。/好吧可能只有我是这么想的/
然后哇,大于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;
}
```