首页 > 代码库 > CODEVS1138聪明的质检员2011T5
CODEVS1138聪明的质检员2011T5
题目描述 Description
小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n 个矿石，从1到n 逐一编号，每个矿石都有自己的重量wi 以及价值vi。检验矿产的流程是：见图
若这批矿产的检验结果与所给标准值S 相差太多，就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产，所以他想通过调整参数W 的值，让检验结果尽可能的靠近标准值S，即使得S-Y 的绝对值最小。请你帮忙求出这个最小值。
思路： 题目描述。。。像个新定义的题。。。我真是。。。比较简单，可以看出w越大，y越小。用二分，每次都更新前缀和数组，然后计算，比较左右端点和终点时计算的值和s的关系，然后进行下去，直到左右端点相邻。
code：
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int v[200001]={0},w[200001]={0},li[200001]={0},ri[200001]={0};
long long sum[200001]={0},vv[200001]={0};
int main()
{
int i,j,n,m,mid,ll=0,rr=0;
long long s=0,ans=0,ans1=0,ans2=0;
scanf("%d%d%lld",&n,&m,&s);
for (i=1;i<=n;++i)
{
scanf("%d%d",&w[i],&v[i]);
if (w[i]>rr) rr=w[i];
sum[i]=sum[i-1]+1;
vv[i]=vv[i-1]+v[i];
}
for (i=1;i<=m;++i)
{
scanf("%d%d",&li[i],&ri[i]);
--li[i];
ans1=ans1+(vv[ri[i]]-vv[li[i]])*(sum[ri[i]]-sum[li[i]]);
}
++rr;
ll=1;
while (ll<rr-1)
{
mid=(ll+rr)/2;
for (i=1;i<=n;++i)
{
sum[i]=sum[i-1];
if (w[i]>=mid)
++sum[i];
}
for (i=1;i<=n;++i)
{
vv[i]=vv[i-1];
if (w[i]>=mid)
vv[i]+=v[i];
}
ans=0;
for (i=1;i<=m;++i)
ans+=(sum[ri[i]]-sum[li[i]])*(vv[ri[i]]-vv[li[i]]);
if (ans>=s&&s>=ans2)
{
ll=mid;
ans1=ans;
}
if (ans<=s&&s<=ans1)
{
rr=mid;
ans2=ans;
}
}
ans=min(abs(ans1-s),abs(ans2-s));
printf("%lld\n",ans);
} CODEVS1138聪明的质检员2011T5
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。