P1740聰明的質檢員
Accepted
标簽:
其他 二分查找
NOIP提高組2011
描述
小 T 是一名品質監督員,最近負責檢驗一批礦産的品質。這批礦産共有n個礦石,從1到n逐一編号,每個礦石都有自己的重量wi以及價值vi。檢驗礦産的流程是:
1、給定m個區間[Li,Ri];
2、選出一個參數W;
3、對于一個區間[Li,Ri],計算礦石在這個區間上的檢驗值Yi:
Yi=(∑j1)∗(∑jvj) , j∈[Li,Ri]且wj≥W
j是礦石編号這批礦産的檢驗結果Y 為各個區間的檢驗值之和。即:
Y=∑i=1mYi
若這批礦産的檢驗結果與所給标準值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
樣例輸入1[複制]
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
樣例輸出1[複制]
10
限制
1s
提示
樣例說明:當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。
來源
NOIp2011提高組Day2第二題
解析:二分标準w,然後計算标準為w時的檢驗值(這裡要用到預處理)。
s的讀入弄成%d,wa了好多次。。。。。。
代碼:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<climits>
using namespace std;
typedef long long LL;
const int maxn=2e5;
int n,m;
int w[maxn+20],v[maxn+20];
LL s,sw[maxn+20],sv[maxn+20];
int L[maxn+20],r[maxn+20];
int getin()
{
int ans=0;char tmp;
while(!isdigit(tmp=getchar()));
do ans=(ans<<3)+(ans<<1)+tmp-'0';
while(isdigit(tmp=getchar()));
return ans;
}
long long get(int k)
{
LL i,ans=0;
for(i=1;i<=n;i++)
{
sw[i]=sw[i-1],sv[i]=sv[i-1];
if(w[i]>=k)sv[i]+=v[i],sw[i]++;
}
for(i=1;i<=m;i++)
ans+=(sw[r[i]]-sw[L[i]-1])*(sv[r[i]]-sv[L[i]-1]);
return ans;
}
int main()
{
int i;
scanf("%d%d%I64d",&n,&m,&s);
for(i=1;i<=n;i++)w[i]=getin(),v[i]=getin();
for(i=1;i<=m;i++)L[i]=getin(),r[i]=getin();
int mid,x=w[1],y=w[1];
for(i=2;i<=n;i++)x=min(x,w[i]),y=max(y,w[i]);
LL k,ans=min(abs(get(x)-s),(LL)s);
while(x<=y)
{
if(ans==0)break;
mid=(x+y)/2,k=get(mid);
ans=min(ans,abs(k-s));
if(ans<0)printf("%d \n",mid);
if(k<s)y=mid-1;
else x=mid+1;
}
printf("%I64d\n",ans);
return 0;
}