[Problem description]
小 T 是一名质量监督员, 最近负责检验一批矿产的质量. 这批矿产共有 n 个矿石, 从 1 到 n 逐一编号, 每个矿石都有自己的重量 wi 以及价值 vi. 检验矿产的流程是:
1, 给定 m 个区间[Li,Ri];
2, 选出一个参数 W;
3, 对于一个区间[Li,Ri], 计算矿石在这个区间上的检验值 Yi :
这批矿的检验结果 Y 为各个区间的检验值之和. 即:
若这批矿产的检验结果与所给标准值 S 相差太多, 就需要再去检验另一批矿产. 小 T 不想费时间去检验另一批矿产, 所以他想通过调整参数 W 的值, 让检验结果尽可能的靠近标准值 S, 即使得 S-Y 的绝对值最小. 请你帮忙求出这个最小值.
[Input format]
第一行包含三个整数 n,m,S, 分别表示矿石的个数, 区间的个数和标准值.
接下来的 n 行, 每行 2 个整数, 中间用空格隔开, 第 i+1 行表示 i 号矿石的重量 wi 和价值 vi .
接下来的 m 行, 表示区间, 每行 2 个整数, 中间用空格隔开, 第 i+n+1 行表示区间 [Li,Ri] 的两个端点 Li 和 Ri. 注意: 不同区间可能重合或相互重叠.
[Output format]
输出只有一行, 包含一个整数, 表示所求的最小值.
[Algorithm design]
二分答案 + 前缀和
[Problem analysis]
求最接近标准的答案, 很明显二分答案. 当然二分 Y 明显很困难, 应该分治 W 的值. 这里又可以引入离散化思想, 因为 W 一定是一个矿的质量, 不然不会有变化. 确定 W 之后就是怎么求 Y 的问题, 首先要读懂题目, 其实意思很简单, 就是一个区间内可行矿的数量 * 可行矿的价值总和, 因为区间老是重叠, 如果循环处理, 最大可能达到 O(nm), 所以想到前缀和处理, 纪录 1 到 i 的可行矿数量和价值总和 (一开始还想到线段树..), 最后就是 O((n+m)logn) 的算法
- [Source code]
- #include <bits/stdc++.h>
- #define MAXN 200010
- #define ll long long
- using namespace std;
- int n,m;
- ll s,ans,sumx[MAXN];
- int w[MAXN],v[MAXN],b[MAXN],e[MAXN],sortw[MAXN],sum[MAXN];
- void search(int l,int r)
- {
- if(l==r-1)
- return ;
- int mid=(l+r)>>1;
- ll y=0;
- for(int i=1;i<=n;i++)
- {
- sum[i]=sum[i-1];
- sumx[i]=sumx[i-1];
- if(w[i]>=sortw[mid])
- sum[i]+=1,sumx[i]+=v[i];
- }// 在 W 确定后处理出前缀和
- for(int i=1;i<=m;i++)
- y+=(sum[e[i]]-sum[b[i]-1])*(sumx[e[i]]-sumx[b[i]-1]);// 利用前缀和处理出 Y
- ans=min(ans,abs(y-s));// 比较后纪录最小差值
- if(y<s)
- search(l,mid);
- else
- search(mid,r);
- }
- int main()
- {
- freopen("qc.in","r",stdin);
- freopen("qc.ans","w",stdout);
- cin>>n>>m>>s;
- for(int i=1;i<=n;i++)
- cin>>w[i]>>v[i],sortw[i]=w[i];
- for(int i=1;i<=m;i++)
- cin>>b[i]>>e[i];
- sort(sortw+1,sortw+n+1);// 将矿值排序以便于二分
- ans=1000000000001;
- search(0,n+1);
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2712154.html