Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


NOIP 聪明的质检员

题目链接 点这里

题目描述

小T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有 n 个矿石,从 > 1到n 逐一编号,每个矿石都有自己的重量 wi 以及价值vi 。检验矿产的流程是:
1 、给定m 个区间[Li,Ri];
2 、选出一个参数 W;
3 、对于一个区间[Li,Ri],计算矿石在这个区间上的检验值Yi:
tu
这批矿产的检验结果Y 为各个区间的检验值之和。即:Y1+Y2…+Ym
若这批矿产的检验结果与所给标准值S 相差太多,就需要再去检验另一批矿产。小T
不想费时间去检验另一批矿产,所以他想通过调整参数W 的值,让检验结果尽可能的靠近
标准值S,即使得S-Y 的绝对值最小。请你帮忙求出这个最小值。


输入输出格式

输入格式

输入文件qc.in 。

第一行包含三个整数n,m,S,分别表示矿石的个数、区间的个数和标准值。

接下来的n 行,每行2个整数,中间用空格隔开,第i+1 行表示 i 号矿石的重量 wi 和价值vi。

接下来的m 行,表示区间,每行2 个整数,中间用空格隔开,第i+n+1 行表示区间[Li,Ri]的两个端点Li 和Ri。注意:不同区间可能重合或相互重叠。

输出格式

输出文件名为qc.out。

输出只有一行,包含一个整数,表示所求的最小值。


一道比较简单的二分答案的题 观察得知w参数的变化使得Y具有单调性 所以由此可以想到二分w

而数据n m都是小于200000 所以直接开sum[i][j]表示i到j比w大的个数和价值和肯定不行 由此我们又想到了前缀和思想

sum1表示从1到i比w大的个数,sum2表示从1到i比w大的价值总和

由此

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<queue>
#include<deque>
#include<stack>
#define LL long long
using namespace std;
void read(int &x){
char c = getchar(); x = 0;
while(c < '0' || c > '9') c = getchar();
while(c <= '9' && c >= '0') x = x*10+c-48, c = getchar();
}
LL S,ans = 1e12;
int n,m;
int l[200005],r[200005],w[200005],v[200005];
LL sum[200005],cnt[200005];
LL work(int W){
LL y = 0;
for(int i = 1;i <= n;i++){
sum[i] = sum[i-1];
cnt[i] = cnt[i-1];
if(w[i] > W){
sum[i] += v[i];
cnt[i]++;
}
}
for(int i = 1;i <= m;i++)
y += (sum[r[i]]-sum[l[i]-1]) * (cnt[r[i]]-cnt[l[i]-1]);
return y;
}
int main(){
freopen("data.txt","r",stdin);
read(n),read(m);scanf("%lld",&S);
for(int i = 1;i <= n;i++)
read(w[i]),read(v[i]);
for(int i = 1;i <= m;i++)
read(l[i]),read(r[i]);
int ll = 1,rr = 1e6;
while(ll < rr){
int mid = (ll+rr)>>1;
LL Y = work(mid);
ans = min(ans,abs(Y-S));
if(Y > S) ll = mid+1;
else rr = mid;
}
printf("%lld",ans);
return 0;
}

Markdown

最近的文章

读入输出优化

很多dalao都用这个,挺方便的12345678910111213 void read(int &amp;x)&#123; char c = getchar(); x = 0; while(c &lt; '0' || c &gt; '9') c = getchar(); while …

于 继续阅读
更早的文章

(动规DP,背包)汇总

环形DP这种区间DP,先枚举划分段是很不好的最好是先枚举位置,这样就由位置先限制住了划分的段数,避免了冗余也避免了无解情况计算其中导致乘爆掉…在C/C++或者pascal里面负数对正数取模的结果还是负数。所以需要再多一步负数判断把它弄成正的。。 例题1Vijosp1218数字游戏比较水 123456 …

于  DP 继续阅读