渔民的烦恼 （二分）

题目大意

• 在某个海边小国，大多数居民都是渔民，这个国家的所有城镇都沿直线分布在海边。渔民们捕获大量的海鱼，但就象世界上大多数的渔民一样，他们并不喜欢吃鱼，所以他们决定从邻国收养一些贫困家庭的小孩，让他们来帮着吃鱼，国家规定每个城镇收养的贫困儿童数量必须相等。
• 一条又长又直的公路贯穿整个海岸将所有的城镇连接了起来，所以每个城镇（除去第一个和最后一个）都直接和相邻的两个城镇相连接。一个小孩一年要吃掉一吨鱼，每个城镇捕获的鱼既可以在本地吃也可以运往其它城市吃，在运输过程中，每公里要上交一吨鱼作为过路费。
• 已知每个城镇一年的捕鱼产量，并假设运输方案是最佳的，计算最多能收奍多少个贫困儿童。

输入格式

• 第一行包含一个整数N，其中 1≤N≤100,000，表示城镇总数。
• 接下来的 N 行每行包含两个整数 A 和 B ，其中 1≤A≤1,000,000,000, 0≤B≤1,000,000,000，分别表示城镇的位置(坐标)和该城镇的捕鱼产量，所有城镇按其位置从小到大排序给出，注意问题一定存在正整数解。

输出格式

• 输出文件仅一行，包含一个整数表示每个城镇最多能够收养的贫困儿童数量。

样例

样例输入

4
20 300
40 400
340 700
360 600

样例输出

415

算法分析

• 很明显的二分的答案
• 很好想
• 直接看代码
• 算了还是说两句吧 ： 首先我们这里的核心是cnt 关于每个位置我们按顺序扫一遍 从第一个点开始扫 扫到最后一个点
• cnt表示扫到当前点时 是有多余的鱼还是鱼不够 很显然如果到当前点 cnt<0 表示鱼不够 那么想要让鱼运过来首先要走下面那条路 然后就要加路的边权
• 如果当前的cnt > 0呢？ 有两种情况 如果当前的鱼够接下来要走的路的路费 那么显然运走会更优 如果不够运费呢？（那宁运宁马呢） 显然就不用运过去了 ，所以如果cnt > 0是会有两种转移情况的

代码展示

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
ll Max,Min = 0x3f3f3f3f;
ll loc[maxn],v[maxn],w[maxn],ans;

int main(){
    ll n;scanf("%lld",&n);
    for(ll i = 1;i <= n;++i){scanf("%lld%lld",&loc[i],&v[i]);Min = min(Min,v[i]);Max = max(Max,v[i]);}
    ll l = Min,r = Max;
    while(l <= r){//二分答案
        ll mid = (l + r) >> 1;
        ll cnt = v[1] - mid;//初始化cnt的值
        for(ll i = 2;i <= n;++i){
                if(cnt < 0) cnt -= loc[i] - loc[i-1] + mid - v[i];//减去来到当前点的路费 然后加上当前点的权值
                else if(cnt >= 0) cnt = max(cnt - (loc[i] - loc[i-1]),(ll)0) + v[i] - mid;//是否转移过来 如果鱼够运费那就运过来
        }
        if(cnt < 0) r = mid-1;//如果cnt小于0 表示当前状态不满足
        if(cnt >= 0) {l = mid + 1;ans = mid;}//cnt大于0 表示当前状态可满足
    }
    printf("%lld\n",ans);
    return 0;
}