描述

小T?是一名質量監督員，最近負責檢驗一批礦產的質量。這批礦產共有?n?個礦石，從?1到n?逐一編號，每個礦石都有自己的重量?wi?以及價值vi?。檢驗礦產的流程是：?
1?、給定m?個區間[Li?，Ri]；?
2?、選出一個參數?W；?
3?、對于一個區間[Li?，Ri],計算礦石在這個區間上的檢驗值Yi:
Yi=Σ1*Σvj，Σ的循環變量為j，這里j要滿足j∈[Li,Ri]且wj≥W，這里j是礦石編號。

這批礦產的檢驗結果Y為各個區間的檢驗值之和。ΣYi，Σ的循環變量為i，1≤i≤m。

若這批礦產的檢驗結果與所給標準值S?相差太多，就需要再去檢驗另一批礦產。小T不想費時間去檢驗另一批礦產，所以他想通過調整參數W?的值，讓檢驗結果盡可能的靠近標準值S，即使得S-Y?的絕對值最小。請你幫忙求出這個最小值。?

輸入格式

第一行包含三個整數n?，m，S，分別表示礦石的個數、區間的個數和標準值。?接下來的n?行，每行?2?個整數，中間用空格隔開，第i+1?行表示?i?號礦石的重量?wi?和價值vi?。?
接下來的m?行，表示區間，每行2?個整數，中間用空格隔開，第i+n+1?行表示區間[Li,?Ri]的兩個端點?Li?和Ri?。注意：不同區間可能重合或相互重疊。?

輸出格式

輸出只有一行，包含一個整數，表示所求的最小值。?

測試樣例1

輸入

5 3 15?
1 5?
2 5?
3 5?
4 5?
5 5?
1 5?
2 4?
3 3

輸出

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?。? 注意區間的處理，每次檢查都要再算一遍前綴和 #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; const int maxn = 220005; struct STONE{long long w;long long v; }; long long n,m,s,l[maxn],r[maxn],sum[maxn],sumv[maxn],all,ans = 98765432112345L; STONE stone[maxn]; void input(){cin>>n>>m>>s;all = 0;for(int i = 1;i <= n;i++){scanf("%lld%lld",&stone[i].w,&stone[i].v);if(all < stone[i].w) all = stone[i].w;}for(int i = 1;i <= m;i++){scanf("%lld%lld",&l[i],&r[i]);} } bool check(long long t){sum[0] = sumv[0] = 0;for(int i = 1;i <= n;i++){if(stone[i].w >= t){sumv[i] = sumv[i-1] + stone[i].v;sum[i] = sum[i-1] + 1;}else{sumv[i] = sumv[i-1];sum[i] = sum[i-1];}}all = 0;for(int i = 1;i <= m;i++){all += (sumv[r[i]] - sumv[l[i]-1]) * (sum[r[i]] - sum[l[i]-1]);}ans = min(abs(all - s),ans);return all < s; } void div(){long long lans = 0,rans = all,mans;while(lans <= rans){mans = (lans + rans) >> 1;if(check(mans)){rans = mans - 1;}else{lans = mans + 1;}}check(mans+1);if(mans > 0)check(mans-1);cout<<ans; } int main(){input();div();return 0; } View Code

?

轉載于:https://www.cnblogs.com/hyfer/p/5656217.html

總結

以上是生活随笔為你收集整理的NOIP2011 聪明的质监员的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。