2018-2019 ACM-ICPC, Asia Seoul Regional Contest E题(分段函数二分)
此题也属于二分经典应用,分段函数。
先按v(即x轴)从小到大排序 。
此题还用到了一个数学小点:假设现在有两根线,纵坐标较大值为maxx, 较小值为minn, 两根线之间的点距离上下边界不超过mid - minn(也可表述为maxx - mid),mid = (maxx + minn) / 2。
此题的check函数,对于传入的x(当前假设最小误差值),先初始化maxx = minn = 第一个点的纵坐标y1,然后遍历后续的点时更新两根线的上下界,每更新完计算此时的 maxx - minn <= 2 * x 还是 > 2 * x, 如果>2 * x,则进入下一区间,以当前该点的纵坐标更新maxx, minn。遍历结束后如果产生>3个区间,说明x值偏小,导致区间个数偏多,否则可以减小x。
还有,题目让保留一位小数,所以可以将每个l值*10进行二分,这样二分结果为扩大了10倍,最后结果再% 10求出小数部分,/ 10求出整数部分。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 3e5 + 10;
typedef long long ll;
struct Node
{
ll v, l;
}node[maxn];
int n;
bool cmp(Node a, Node b)
{
return a.v < b.v;
}
bool check(ll x)
{
int i = 0;
for(i; i < n; i++)
{
if(node[i].l > x)
break;
}
if(i == n) return true;
int l1;
ll minn = node[i].l, maxx = node[i].l;
for(i; i < n; i++)
{
minn = min(minn, node[i].l);
maxx = max(maxx, node[i].l);
if(maxx - minn > 2 * x)
break;
l1 = (minn + maxx) / 2;
}
if(i >= n) return true;
int l2;
minn = node[i].l, maxx = node[i].l;
for(i; i < n; i++)
{
minn = min(minn, node[i].l);
maxx = max(maxx, node[i].l);
if(maxx - minn > 2 * x)
break;
l2 = (minn + maxx) / 2;
}
if(i < n) return false;
return l2 >= l1;
}
int main()
{
while(scanf("%d", &n) != EOF)
{
ll base = 0;
for(int i = 0; i < n; i++)
{
scanf("%I64d%I64d", &node[i].v, &node[i].l);
node[i].l *= 10;
if(node[i].v == 0)
base = max(base, node[i].l);
}
sort(node, node + n, cmp);
ll l = 0, r = 1e10; //注意,l值已经乘10了,所以上界也要乘10!1e9WA了
ll mid;
ll res;
while(l <= r)
{
mid = l + (r - l) / 2;
bool f = check(mid);
if(f)
{
r = mid - 1; res = mid;
//必须用res保存值,因为可能出现就无解的情况,所以需要确保f为true才能赋值。但是如果直接用mid作为答案,mid是一定存在的(l + r / 2)嘛
}
else l = mid + 1;
}
ll ans = max(base, res);
ll x = ans % 10;
ans = ans / 10;
printf("%I64d.%I64d\n", ans, x);
}
return 0;
}