回顾-二分

洛谷 1314 聪明的质监员
题意：数学公式，有n个产品 重量w 价值v，求m个区间里

（区间中 产品重量比W重的个数）*（区间中 产品重量比W重的产品价值的和）再将各个区间的yi加起来 就是Y。工厂的标准是s，找到一个W，使|Y-s|最小
分析：看到找到各种条件和与s最小，想到了二分,各个区间的和–前缀和。
前缀和
假设W，和所有产品使用yi，使用前缀和，找到各个位置W V方便求区间
[l,r]的和 == sum[r]-sum[l-1];（一定是l-1）

二分
我们很容易发现，W=0时，所有矿石都可以选上
当W大于最大重量时，一个都选不上
W值越大，选上的矿石越少，相反W值越小，选上的矿石越多
对应 W值越大，Y越小
所以 找到二分条件
Y>s 增大W来减小Y 减小|Y-s|
Y==s |Y-s|=0
Y<s 减小W来增大Y 减小|Y-s|

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

typedef pair<int,int>Pair;
const int N = 2e5+10;

int n,m;
long long s;
int w[N],v[N];
long long ww[N],vv[N];
long long ss;
vector<Pair>ve;

bool check(int W)
{
    long long sum=0,l=ve.size();
    memset(ww,0,sizeof(ww));
    memset(vv,0,sizeof(vv));

    for(int i=1;i<=n;i++)
    {
        if(w[i]>=W)ww[i]=ww[i-1]+1,vv[i]=vv[i-1]+v[i];
        else ww[i]=ww[i-1],vv[i]=vv[i-1];
    }
    for(int i=0;i<l;i++)
    {
        sum+=(ww[ve[i].second]-ww[ve[i].first-1])*(vv[ve[i].second]-vv[ve[i].first-1]);
    }
    //cout<<W<<' '<<sum<<endl;
    ss=fabs(sum-s);
    if(sum>s)
        //cout<<W<<' '<<ss<<endl;
        return true;
    else
        return false;
}

int main()
{
    int l=2147483647,r=-1,mid;
    scanf("%d%d%lld",&n,&m,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&w[i],&v[i]);
        r=max(r,w[i]);
        l=min(l,w[i]);
    }
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        ve.push_back(Pair{a,b});
    }
    long long ans=0x3f3f3f3f3f3f3f3f;
    while(l<r)
    {
        mid=(l+r+1)>>1;//不加+1 会死循环
        //cout<<i<<' '<<j<<' '<<mid<<endl;
        if(check(mid))l=mid;
        else r=mid-1;
        ans=min(ans,ss);
    }
    //printf("%d\n",l);
    printf("%lld\n",ans);

    return 0;
}

洛谷1281 书的复制
题意：有n种书，m个人，设计一种方案，一本书只能分给一个人，将n本书分配给m个人，前面尽量少分配，使得复制时间最短，复制时间为抄写页数最多的人用去的时间
分析：使用二分 判定性质：按照x 分配任务，是否可以分配给m个人,找到最短最长的时间，按照时间去分任务，输出

#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
using namespace std;

const int N = 600;
int n,m;
long long a[N];
int d[N][2],c=0;

bool check(int x)
{
    int s=1;
    long long sum=0;
    for(int i=n-1;i>=0;i--)
    {
        sum+=a[i];
        if(sum>x)
        {
            s++;
            sum=a[i];
        }
    }
    if(s>m)return false;
    else return true;
}

void print(int x)//输出写的有点麻烦
{
    int s=n-1,sum=0;
    for(int i=n-1;i>=0;i--)
    {
        sum+=a[i];
        if(sum>x)
        {
            //printf("%d %d\n",i+2,s+1);
            d[c][0]=i+2;
            d[c][1]=s+1;
            c++;
            sum=a[i];
            s=i;
            continue;
        }
        if(sum==x)
        {
            //printf("%d %d\n",i+1,s+1);
            sum=0;
            d[c][0]=i+1;
            d[c][1]=s+1;
            c++;
            s=i-1;
            continue;
        }
        if(i==0)
        {
            //printf("%d %d\n",i+1,s+1);
            d[c][0]=i+1;
            d[c][1]=s+1;
            c++;
        }
    }
    for(int i=c-1;i>=0;i--)
        printf("%d %d\n",d[i][0],d[i][1]);
}

int main()
{
    scanf("%d%d",&n,&m);
    long long sum=0;
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]),sum+=a[i];

    long long i=1,j=sum,mid;

    while(i<j)
    {
        mid=(i+j)>>1;
        //cout<<i<<'+'<<j<<' '<<mid<<endl;
        if(check(mid))j=mid;
        else i=mid+1;
    }
    print(i);
    //printf("%d\n",i);
    //cout<<s<<endl;

    return 0;
}