|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- #include<bits/stdc++.h>
- using namespace std;
- // #define INF 0X3f3f3f3f
- typedef long long ll;
- ll s,n,m,ans=1e18;
- vector<int>w,v,l,r;
- vector<ll> sn,sv;
- bool check(int W)
- {
- sn.assign(n+1, 0);
- sv.assign(n+1, 0);
- for(int i=1;i<=n;i++)
- {
- if(w[i]>=W)sn[i]=sn[i]+1,sv[i]=sv[i-1]+v[i];
- else sn[i]=sn[i-1],sv[i]=sv[i-1];
- }
- ll y=0;
- for(int i=1;i<=m;i++)
- {
- y+=(sn[r[i]]-sn[l[i]-1])*(sv[r[i]]-sv[l[i]-1]);
- }
- ans=min(ans,llabs(y-s));
- return y<=s; //w大那么y就小
- }
- ll find()
- {
- // ll ans=0;
- int l=0,r=1e6+1;
- while(l+1<r)
- {
- ll mid=l+r>>1;
- if(check(mid))r=mid;
- else l=mid;
- }
- return ans;
-
- }
- int main()
- {
- cin>>n>>m>>s;
- w.resize(n);
- v.resize(n);
- l.resize(m);
- r.resize(m);
- for(int i=0;i<n;i++)
- {
- cin>>w[i]>>v[i];
- }
- for(int i=0;i<m;i++)
- {
- cin>>l[i]>>r[i];
- }
- cout<<find()<<endl;
- }
复制代码 |
|