OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【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层最少能由多少段组成。

【输入样例】

1 1

【输出样例】

1

【数据范围】

对于100%的数据满足1≤k≤n≤100。

【题解】

目测所有函数都是单调函数时结果最优,而单调函数中最简单的就是一次函数……

喏,先找规律好了。




可以看出除了最高层外,从下往上构成了等差数列,第t层为t*2段。注意到若k>n-k+1,可以把图形倒过来,所以答案是min(k,n-k+1)*2。

注意特判n=1的情况,这时候只有一段。

【代码】

1A~~~

http://paste.ubuntu.com/8505344/

评论
热度(1)

© OI技术宅 | Powered by LOFTER