首页 > 代码库 > [NOIP2011]聪明的质检员
[NOIP2011]聪明的质检员
【问题描述】
小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有$n$个矿石，从 1 到$n$逐一编号，每个矿石都有自己的重量$w_i$以及价值$v_i$。检验矿产的流程是：
1. 给定 m个区间$[L_i, R_i]$；
2. 选出一个参数$W$；
3. 对于一个区间$[L_i, R_i]$，计算矿石在这个区间上的检验值$Y_i $：
\[ Y_i = \sum_j 1 \times \sum_j v_j , j \in [L_i, R_i] \text{且} w_j \ge W, j \text{是矿石编号} \]
这批矿产的检验结果$Y$为各个区间的检验值之和。即：
\[ Y = \sum_{i=1}^{m} Y_i \]
若这批矿产的检验结果与所给标准值 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。
输出只有一行，包含一个整数，表示所求的最小值。
【输入输出样例】
qc.in
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
qc.out
10
【输入输出样例说明】
当W 选4 的时候，三个区间上检验值分别为20、5、0，这批矿产的检验结果为25，此时与标准值S 相差最小为10。
【数据范围】
对于10%的数据，有1≤n，m≤10；
对于30%的数据，有1≤n，m≤500；
对于50%的数据，有1≤n，m≤5,000；
对于70%的数据，有1≤n，m≤10,000；
对于100%的数据，有1≤n，m≤200,000，0 < wi, vi≤10^6，0 < S≤10^12，1≤Li≤Ri≤n。
【分析】
二分答案，扫一遍求前缀和，利用前缀和O(1)计算每个区间的检验值。总时间复杂度$O((m + n) * log_2 W)$。在实现中还可以离散化所有的W，消除运行时间对参数W的依赖，还可以记录下当前已经计算到了哪一点，统计时只需添加或删除当前参数与所求参数之间的那段就可以了。这样，所有”标记“所需的时间就可以降为$O(n)$。于是总时间复杂度就变成了$O(n + mlog_2 n)$。
最后剩下一点细节：二分答案找到的Y不保证距离S最近，因此我们还要取在S另一边的一个Y做判断，输出较小的那个即可。
最后剩下一点细节：二分答案找到的Y不保证距离S最近，因此我们还要取在S另一边的一个Y做判断，输出较小的那个即可。
1 /*=============================================================================================================================*/
2 /*======================================================Code by Asm.Def========================================================*/
3 /*=============================================================================================================================*/
4 #include <cstdio>
5 #include <iostream>
6 #include <algorithm>
7 #include <cmath>
8 #include <cctype>
9 #include <memory.h>
10 #include <vector>
11 #include <set>
12 #include <string>
13 #include <cstring>
14 #include <map>
15 #include <queue>
16 #include <deque>
17 #include <stack>
18 #include <ctime>
19 #include <iterator>
20 #include <functional>
21 #include <cstdlib>
22 using namespace std;
23 #define forall(it,v) for(__typeof(v.begin()) it = v.begin();it < v.end();++it)
24 #define pb push_back
25 #define REP(i,j,k) for(i = j;i <= k;++i)
26 #define REPD(i,j,k) for(i = j;i >= k;--i)
27 typedef long long LL;
28 #if defined DEBUG
29 FILE *in = fopen("test", "r");
30 #define out stdout
31 #else
32 FILE *in = fopen("qc.in","r");
33 FILE *out = fopen("qc.out","w");
34 #endif
35 template <typename T>
36 void getint(T &x){
37 char c = fgetc(in);
38 while(!isdigit(c))c = fgetc(in);
39 x = c - ‘0‘;
40 while(isdigit(c = fgetc(in)))x = x * 10 + c - ‘0‘;
41 }
42 /*==============================================WORK===========================================================*/
43 const int maxn = (int)2e5 + 4;
44
45 inline void putLL(const LL&x){
46 if(x < 1000000000){fprintf(out, "%d\n", x);return;}
47 int l = x / 1000000000, r = x % 1000000000;
48 fprintf(out, "%d%09d\n", l, r);
49 }
50
51 struct Obj{
52 int w, v, loc;
53 bool operator < (const Obj &b)const{
54 return w > b.w;
55 }
56 }O[maxn] = {{0,0,0}};
57 int n, m, L[maxn], R[maxn], now = 0, Sumcnt[maxn] = {0};
58 LL S, SumV[maxn] = {0};
59 int V[maxn] = {0};//用于计算"价格"前缀和 & 个数前缀和
60 inline LL f(int W){///////////////////////////////////////////////////
61 LL ans = 0; SumV[0] = 0;Sumcnt[0] = 0;
62 int i;
63 if(O[now].w > W) while(now < n && O[now+1].w >= W)
64 ++now, V[O[now].loc] = O[now].v;
65 else while(now && O[now].w < W)
66 V[O[now].loc] = 0, --now;
67 for(i = 1;i <= n;++i)
68 SumV[i] = SumV[i-1] + V[i], Sumcnt[i] = Sumcnt[i-1] + bool(V[i]);
69 for(i = 0;i < m;++i)
70 ans += (SumV[R[i]] - SumV[L[i]-1]) * (Sumcnt[R[i]] - Sumcnt[L[i]-1]);
71 return ans;
72 }
73 int main(){
74 int i, j = 0, k;
75 LL ans, t, t2;
76 int Wcase[maxn] = {0}, Wcnt = 0;
77 getint(n), getint(m), getint(S);
78 for(i = 1;i <= n;++i){
79 getint(O[i].w), getint(O[i].v);
80 O[i].loc = i;
81 }
82 sort(O + 1, O + n + 1);
83 O->w = O[1].w + 1;
84 for(i = 0;i < m;++i)
85 getint(L[i]), getint(R[i]);
86 for(i = 1;i <= n;++i)
87 if(!Wcnt || O[i].w != Wcase[Wcnt-1])
88 Wcase[Wcnt++] = O[i].w;
89 i = 0, j = Wcnt-1;
90 while(i <= j){
91 k = (i + j) >> 1;
92 t = f(Wcase[k]);
93 if(t == S){ans = 0;break;}
94 if(t > S)j = k - 1;
95 else i = k + 1;
96 }
97 ans = S > t ? S - t : t - S;
98 t2 = f(Wcase[i ^ j ^ k]);//i ^ j ^ k表示i和j中不等于k的那一个
99 t2 = S > t2 ? S - t2 : t2 - S;
100 if(t2 < ans)ans = t2;
101 putLL(ans);
102 //----------------------------------------------------------------------------------------------------------------------
103 #if defined DEBUG
104 cout << endl << (double)clock() / CLOCKS_PER_SEC <<endl;
105 #endif
106 return 0;
107 }
108 /*=============================================================================================================================*/
2 /*======================================================Code by Asm.Def========================================================*/
3 /*=============================================================================================================================*/
4 #include <cstdio>
5 #include <iostream>
6 #include <algorithm>
7 #include <cmath>
8 #include <cctype>
9 #include <memory.h>
10 #include <vector>
11 #include <set>
12 #include <string>
13 #include <cstring>
14 #include <map>
15 #include <queue>
16 #include <deque>
17 #include <stack>
18 #include <ctime>
19 #include <iterator>
20 #include <functional>
21 #include <cstdlib>
22 using namespace std;
23 #define forall(it,v) for(__typeof(v.begin()) it = v.begin();it < v.end();++it)
24 #define pb push_back
25 #define REP(i,j,k) for(i = j;i <= k;++i)
26 #define REPD(i,j,k) for(i = j;i >= k;--i)
27 typedef long long LL;
28 #if defined DEBUG
29 FILE *in = fopen("test", "r");
30 #define out stdout
31 #else
32 FILE *in = fopen("qc.in","r");
33 FILE *out = fopen("qc.out","w");
34 #endif
35 template <typename T>
36 void getint(T &x){
37 char c = fgetc(in);
38 while(!isdigit(c))c = fgetc(in);
39 x = c - ‘0‘;
40 while(isdigit(c = fgetc(in)))x = x * 10 + c - ‘0‘;
41 }
42 /*==============================================WORK===========================================================*/
43 const int maxn = (int)2e5 + 4;
44
45 inline void putLL(const LL&x){
46 if(x < 1000000000){fprintf(out, "%d\n", x);return;}
47 int l = x / 1000000000, r = x % 1000000000;
48 fprintf(out, "%d%09d\n", l, r);
49 }
50
51 struct Obj{
52 int w, v, loc;
53 bool operator < (const Obj &b)const{
54 return w > b.w;
55 }
56 }O[maxn] = {{0,0,0}};
57 int n, m, L[maxn], R[maxn], now = 0, Sumcnt[maxn] = {0};
58 LL S, SumV[maxn] = {0};
59 int V[maxn] = {0};//用于计算"价格"前缀和 & 个数前缀和
60 inline LL f(int W){///////////////////////////////////////////////////
61 LL ans = 0; SumV[0] = 0;Sumcnt[0] = 0;
62 int i;
63 if(O[now].w > W) while(now < n && O[now+1].w >= W)
64 ++now, V[O[now].loc] = O[now].v;
65 else while(now && O[now].w < W)
66 V[O[now].loc] = 0, --now;
67 for(i = 1;i <= n;++i)
68 SumV[i] = SumV[i-1] + V[i], Sumcnt[i] = Sumcnt[i-1] + bool(V[i]);
69 for(i = 0;i < m;++i)
70 ans += (SumV[R[i]] - SumV[L[i]-1]) * (Sumcnt[R[i]] - Sumcnt[L[i]-1]);
71 return ans;
72 }
73 int main(){
74 int i, j = 0, k;
75 LL ans, t, t2;
76 int Wcase[maxn] = {0}, Wcnt = 0;
77 getint(n), getint(m), getint(S);
78 for(i = 1;i <= n;++i){
79 getint(O[i].w), getint(O[i].v);
80 O[i].loc = i;
81 }
82 sort(O + 1, O + n + 1);
83 O->w = O[1].w + 1;
84 for(i = 0;i < m;++i)
85 getint(L[i]), getint(R[i]);
86 for(i = 1;i <= n;++i)
87 if(!Wcnt || O[i].w != Wcase[Wcnt-1])
88 Wcase[Wcnt++] = O[i].w;
89 i = 0, j = Wcnt-1;
90 while(i <= j){
91 k = (i + j) >> 1;
92 t = f(Wcase[k]);
93 if(t == S){ans = 0;break;}
94 if(t > S)j = k - 1;
95 else i = k + 1;
96 }
97 ans = S > t ? S - t : t - S;
98 t2 = f(Wcase[i ^ j ^ k]);//i ^ j ^ k表示i和j中不等于k的那一个
99 t2 = S > t2 ? S - t2 : t2 - S;
100 if(t2 < ans)ans = t2;
101 putLL(ans);
102 //----------------------------------------------------------------------------------------------------------------------
103 #if defined DEBUG
104 cout << endl << (double)clock() / CLOCKS_PER_SEC <<endl;
105 #endif
106 return 0;
107 }
108 /*=============================================================================================================================*/
[NOIP2011]聪明的质检员
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。