TIOJ-1406

發表於 更新於 Disqus：

在一個沿海的國家中，所有的村莊都是沿著海岸線分佈的（因此它們連成一條直線）。一條筆直的道路連接起所有沿海的村莊。所有的村莊都可以用一個非負整數表示——代表與道路開端的距離(以公里計)。
大部分的居民從事漁業活動。捕魚季節結束以後，在旅遊季節還沒有開始之前，這些居民所捕的魚可以被運送至不同的城鎮。只要某個城鎮的魚貨儲存量至少有X噸，那麼該城鎮可以提供X位旅客服務。而目標就是盡可能將所有旅客平均的分佈在每個城鎮。換句話說，我們要找出最大的整數Y，使得經過村莊與村莊間的魚貨運送，每一個村莊都至少儲存了Y噸以上的魚。
城鎮與城鎮之間可以運輸整數噸數的魚貨。但是每次在運送時，每載送一公里，就會有山上的搶匪搶走一噸的魚。具體來說，若某個村莊欲運送 F噸的魚到距離D公里遠的另一個村莊，那麼實際到達目的地的魚貨量為 F-D 噸。若F小於D，那麼整批的魚貨將會消失不見。
當然，你可以任意的在某些村莊將這些魚貨重新包裝、組合，然後再運送出去。舉個例子來說，你可以在城鎮C，將從城鎮A和城鎮B運來的魚的各一半，整理一下，然後整批運送到城鎮D，這樣只算是一次運送。

$N\le 10^5, P,F\le 10^{12}$($P$為城鎮的位置，$F$為漁獲)

要greedy的找出Y很難，因此考慮二分搜，對於每個可能的答案我們都能在線性時間檢驗是否可以達到。
題目最後一句頗重要，代表著我們每條路都只會被收最多一次過路費，所以可以維護兩個變數：在這之前所需的量nd及在這之前能供給的量cur。
如果當前的村莊漁獲大於答案，就能讓她消耗nd或加進cur，反之則相反。
迭代到下個村莊前扣掉/加上兩村莊的距離就好。
時間複雜度$\mathcal{O}(nlogC)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
/*-----------------------------------------------------------------------------------------------------*/

bool check(ll x, vector<pair<ll, ll>> &arr) {
	ll nd = 0, cur = 0;
	int n = arr.size();
	for(int i = 0; i < n; i++) {
		if(arr[i].second > x) {
			ll w = min(nd, arr[i].second - x);
			nd -= w;
			cur += arr[i].second - w - x;
		}
		else {
			ll owo = x - arr[i].second;
			ll w = min(cur, owo);
			cur -= w;
			nd += owo - w;
		}
		if(i < n - 1) {
			cur = max<ll>(0, cur - (arr[i + 1].first - arr[i].first));
			if(nd)
				nd += arr[i + 1].first - arr[i].first;
		}
	}
	return (!nd);
}

signed main() {
	EmiliaMyWife
	
	int n;
	while(cin >> n) {
		vector<pair<ll, ll>> arr(n);
		for(int i = 0; i < n; i++)
			cin >> arr[i].first >> arr[i].second;
		ll l = 0, r = 2e12;
		while(l < r) {
			ll m = l + r >> 1;
			if(!check(m, arr))
				r = m;
			else
				l = m + 1;
		}
		cout << l - 1 << '\n';
	}

	return 0;
}