勇者sky遇上的命中注定的恋人白羽竟然是妹妹2

题目大意

构造一个分段函数来拟合若干点（\(x_i , y_i\)），每一段是一个常函数，即

\[f(x)=
\left \{
\begin{aligned}
a_1& & (0\leq x <b_1) \\
a_2& & (b_1\leq x <b_2) \\
&......& \\
a_m& & (b_{m-1} \le x)
\end{aligned}
\right.
\]

误差的定义为

\[E=\max_{1\leq i\leq n} |f(x_i)-y_i|
\]

最小化误差，\(k\)次询问

输入格式

第一行为一个整数\(n\)

后面\(n\)行每行两个自然数，\(x_i,y_i\)

下一行为一个整数\(k\)

后面\(k\)行每行一个正整数\(m_i\)

输出格式

\(k\)行，每行一个整数表示金光第i个询问的答案

\(tips\): 输出可能不为整数

输入样例 #1

2

1 2

5 5

1

1

输出样例 #1

1.5

输入样例 #2

4

1 8

2 19

3 8

4 12

2

2

3

输出样例 #2

5.5

2

输入样例 #3

10

344 9026

762 1512

1463 2024

1688 7200

3832 4384

7225 3868

9048 2158

9706 6899

9812 1720

9851 8398

3

3

1

6

输出样例 #3

2844

3757

2370.5

说明

\(1\leq n\leq 10^6\)

\(0\leq x_i,y_i\leq 10^9,x_i < x_{i+1}\)

\(\sum m\leq 2\times 10^4\)

若V表示值域，每组数据\(n,k,V,\sum m\)小于等于以下值

\[\begin{aligned}
&N\!o.& & n & & k & &V & & \sum m \\
&1&& 10 & & 1 & &100 & & 1\\
&2&& 10 & & 1 & &100 & & 3 \\
&3&& 10 & & 3 & &10^4 & & 10 \\
&4&& 100 & & 1 & &10^5 & & 1 \\
&5&& 100 & & 1 & &10^5 & & 10 \\
&6&& 100 & & 10 && 10^5 & & 100 \\
&7&& 100 && 10 && 10^9& & 100 \\
&8&& 10^4 && 1 && 10^5 && 1 \\
&9&& 10^4 && 1 && 10^5 && 100 \\
&10&& 10^4 && 10 && 10^9& & 100 \\
&11&& 10^5 & &20 && 10^9 && 1000 \\
&12&& 10^5 && 100 && 10^9 && 10^4 \\
&13&& 10^6 && 1 && 10^9 && 1 \\
&14&& 10^6 & &1 & &10^9 & &100 \\
&15&& 10^6 && 10 && 10^9 && 100 \\
&16&& 10^6 && 10 && 10^9 && 2\times 10^4 \\
&17&& 10^6 && 200 && 10^9 && 2\times 10^4 \\
&18&& 10^6 && 200 && 10^9 && 2\times 10^4 \\
&19&& 10^6 && 200 && 10^9 && 2\times 10^4 \\
&20&& 10^6 && 200 && 10^9 && 2\times 10^4 \\
\end{aligned}\]

代码

#include<cstdio>

#include<iostream>

using namespace std;

const int N = 1e6;

int n , y[N + 5] , m , k , Min[N + 5][23] , Max[N + 5][23] , ans;

inline void prepare()

{

	for(register int j = 1; (1 << j) <= n; j++)

		for(register int i = 1; i + (1 << j) - 1 <= n; i++)

		{

			Min[i][j] = min(Min[i][j - 1] , Min[i + (1 << j - 1)][j - 1]);

			Max[i][j] = max(Max[i][j - 1] , Max[i + (1 << j - 1)][j - 1]);

		}

}

inline bool check(int mid , int m)

{

	int l = 1;

	for(register int i = 1; i <= m && l <= n; i++)

	{

		int r = l , smin = y[l] , smax = y[l];

		for(register int j = 22;j >= 0; j--)

		if (r + (1 << j) <= n)

		{

			int tmin = Min[r + 1][j] , tmax = Max[r + 1][j];

			if (max(smax , tmax) - min(smin , tmin) <= mid)

			{

				r += (1 << j);

				smax = max(smax , tmax);

				smin = min(smin , tmin);

			}

		}

		l = r + 1;

	}

	return l > n;

}

inline int work(int m)

{

	int res , l = 0 , r = 1e9 , mid;

	while (l <= r)

	{

		mid = (l + r) >> 1;

		if (check(mid , m)) res = mid , r = mid - 1;

		else l = mid + 1;

	}

	return res;

}

int main()

{

//	freopen("a.in" , "r" , stdin);

	scanf("%d" , &n);

	for(register int i = 1; i <= n; i++)

	{

		scanf("%*d%d" , &y[i]);

		Min[i][0] = Max[i][0] = y[i];

	}

	prepare();

	scanf("%d" , &k);

	while (k--)

	{

		scanf("%d" , &m);

		ans = work(m);

		if (ans & 1) printf("%.1lf\n" , ans * 1.0 / 2);

		else printf("%d\n" , ans / 2);

	}

}

巴特西