题目链接:http://acm.hnucm.edu.cn/JudgeOnline/problem.php?id=1347
二分找最小距离值，让每个小团体移向两边的距离相等，就能得到最小值
判断这个值v是否符合条件：
对于所有的n,使得b[i](b[i]为第i个团体的位置) + v - 起始点 + 1 >= a[i](a[i]为第i个团体人数)
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <map> #include <set> #include <vector> #include <string> #include <cmath> #include <queue> #define rep(i, s, e) for(int i = s; i < e; ++i) #define P pair<int, int> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; static const int N = 35; static const int MAX_N = 1e6 + 5; static const ll Mod = 1e9 + 7; int a[MAX_N], b[MAX_N]; int n; bool judge(int v){ int d = -INF; for(int i = 0; i < n; ++i){ d = max(d, b[i] - v); if(b[i] + v - d + 1 < a[i]) return false; d += a[i]; } return true; } void solve(){ // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); scanf("%d", &n); for(int i = 0; i < n; ++i) scanf("%d", &a[i]); for(int i = 0; i < n; ++i) scanf("%d", &b[i]); int l = 1, r = INF; while(l <= r){ int mid = (l + r) >> 1; if(judge(mid)) r = mid - 1; else l = mid + 1; } printf("%d\n", l); } int main(){ solve(); return 0; }
