[bzoj1432]Function

对于这n个函数，构成了$n(n-1)/2$个交点，对交点离散后，相邻两个交点间函数的编号构成了一个排列，而每一个排列第i个数所构成的段数就是第i层的段数
不妨设初始在-oo处这个排列是1,2,……,n，那么每经过一个交点可以看成是交换两个函数的编号，如果把先小后大看成逆序对，那么相当于是一个不断消除逆序对的过程，最终就变成了n,n-1,……2,1
而我们需要做得就是控制这$n(n-1)/2$次交换的顺序（显然可以任意调整），使得尽量少的变动第k个数，容易推得答案就是2min(k,n-k+1)（特判n=1的情况）

1 #include<bits/stdc++.h>

2 using namespace std;

3 int n,k;

4 int main(){

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

6     if (n==1)printf("1");

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

8 }

巴特西

[bzoj1432]Function

最新文章

热门文章