马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
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,ans=1e18;
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;
}
ans变量定义问题
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3 样例 输出10
为什么ans还是原来的值,怎么修改呢
|