[二分查找]NOIP2011提高組：聰明的質檢員 qc 解題報告

【問題描述】

試題檢視：GoogleDocs

小 T 是一名質量監督員，最近負責檢驗一批礦產的質量。這批礦產共有 n 個礦石，從 1 到 n 逐一編號，每個礦石都有自己的重量 wi 以及價值 vi。檢驗礦產的流程是：

1、給定 m個區間[Li，Ri]；

2、選出一個參數 W；

3、對於一個區間[Li，Ri]，計算礦石在這個區間上的檢驗值 Yi ： 

若這批礦產的檢驗結果與所給標準值 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。

 【分析】

本題的正解是二分W，從0～MaxW+1二分。計算Y時要先預處理，把所有大於W的礦石記錄下來，然後再計算每個區間的值。

二分結束後，找出Min{Get(Right)，Get(Left)}輸出即可。

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
int N,M;
long long S;
const int MAXN=200001;
int W[MAXN];
int V[MAXN];
int L[MAXN];
int Sum[MAXN];
int R[MAXN];
long long TV[MAXN];
int TN[MAXN];
  
void init()
{
    Sum[0]=0;
    cin>>N>>M>>S;
    for (int i=1;i<=N;i++)
    {
        cin>>W[i]>>V[i];
        Sum[i-1]=W[i];
    }
    for (int i=1;i<=M;i++)
        cin>>L[i]>>R[i];
    sort(Sum,Sum+N);
    Sum[N]=Sum[N-1]+1;
}

long long Get(int w)
{
    long long res=0;
    TV[0]=0;
    TN[0]=0;
    for (int i=1;i<=N;i++)
    {
        if(W[i]>=w)
        {
            TV[i]=TV[i-1]+V[i];
            TN[i]=TN[i-1]+1;
            continue;
        }
        else
        {
            TV[i]=TV[i-1];
            TN[i]=TN[i-1];
        }
    }
  
    for (int i=1;i<=M;i++)
    {
        int tl=L[i];
        int tr=R[i];
        long long Temp=(TN[tr]-TN[tl-1])*(TV[tr]-TV[tl-1]);
        res+=Temp;
    }
  
    return res;
}

long long Abs(long long t)
{
    if(t>0)
        return t;
    else
        return -t;
}

void dichotomy()
{
    int Right;
    int Left;
    for (Left=0,Right=N;Left+1<Right;)
    {
        long long Temp=Get(Sum[(Right+Left)/2]);
        if(Temp>=S)
            Left=(Left+Right)/2;
        else
            Right=(Left+Right)/2;
    }
  
    long long TW1,TW2;
    TW1=Abs(Get(Sum[Right])-S);
    TW2=Abs(Get(Sum[Left])-S);
    if(TW2<TW1)
    {
        TW1=TW2;
    }
    cout<<TW1<<endl;
}  

int main()
{
    freopen("qc.in","r",stdin);
    freopen("qc.out","w",stdout);
    init();
    dichotomy();
    return 0;
}