bzoj1432_[ZJOI2009]Function

题目描述

有n 个连续函数fi (x)，其中1 ≤ i ≤ n。对于任何两个函数fi (x) 和fj (x),(i != j)，恰好存在一个x 使得fi (x) = fj (x)，并且存在无穷多的x 使得fi (x) < fj (x)。对于任何i; j; k，满足1 ≤ i < j < k ≤ n，则不存在x 使得fi (x) = fj (x) = fk (x)。

如上左图就是3 个满足条件的函数，最左边从下往上依次为f1; f2; f3。右图中红色部分是这整个函数图像的最低层，我们称它为第一层。同理绿色部分称为第二层，蓝色部分称为第三层。注意到，右图中第一层左边一段属于f1，中间属于f2，最后属于f3。而第二层左边属于f2，接下来一段属于f1，再接下来一段属于f3，最后属于f2。因此，我们称第一层分为了三段，第二层分为了四段。同理第三层只分为了两段。求满足前面条件的n 个函数，第k 层最少能由多少段组成。

输入输出格式

输入格式

一行两个整数n; k。

输出公式

一行一个整数，表示n 个函数第k 层最少能由多少段组成。

样例

INPUT

1 1

OUTPUT

HINT

SOLUTION

(#`O′)喂这样例也太水了点吧。

感谢zzr的友情支持。

推规律：自己多画几个图就出来啦（最好画到\(n=5\)以上吧，不然看不出啥规律），注意一下可以对称翻转整个图形即可。

数学证明：

首先，我们要求的是且仅是\(n\)条线，分出的第\(k\)层的最优解，所以，若能使我们的\(1~n/2\)层有最优解，由于对称性，将整个图形翻转过来之后，我们的\(n/2~n\)层一样也可以有最优解。

然后有一个特判：\(n=1\)时，\(ans=1\)

接下来我们要找的就是上半部分（也可以是下半部分，反正是某半边就可以了对吧）的最优解的求得方法。

数学归纳法证明：

[Warning]其实我并不太熟悉数学归纳法，如果有dalao对这篇题解有问题提出，欢迎一起讨论qwq但这好像姑且算个数学归纳法吧

我们首先可知在\(\forall n\in N_+（n\neq1）\)中，\(k=1时\)一定有\(ans=2\)

\(k>1\)时，对于\(k-1\)层，我们假使结论\(ans=2*(k-1)\)成立，

我们第\(k-1\)层现有的\(2*(k-1)\)段的每一段向原延伸方向延伸直至碰到下一个交点为止，于是得到了新的\(2*(k-1)\)段，而我们又知道，一个交点涉及的的有且只有两条直线，而易得我们每一层的两端必定是由无限远延伸来的射线，因为出现过的直线的线段就是由一个端点延伸而来，故这两条射线所在的直线应该是第一次出现，不能包含在原有的\(2*(k-1)\)段里，所以可以得出，对于第\(k\)层，我们有\(ans=2*k\)

命题得证。

#include <cstdio>

#include <iostream>

using namespace std;

int main(){

	int n,k;

	scanf("%d%d",&n,&k);

	if (n==1) {puts("1");return 0;}

	printf("%d\n",min(k*2,2*(n-k+1)));

	return 0;

}

巴特西