T4

· · 题解

折线函数的图像问题：

考察 \sum\limits_{i=1}^n2|x-a_i|+p\times x 的图像，求最低点位置对应的最小的横坐标。

不妨先对序列a从小到大排序得到序列b。

$b_1<x<b_2$ 时，$|x-b_1|$ 的符号由负转正，对应函数的斜率为 $-2*n+p+4*1$ 。 $b_2<x<b_3$ 时，$|x-b_2|$ 的符号由负转正，对应函数的斜率为 $-2*n+p+4*2$ 。 类推归纳得 $b_i<x<b_{i+1}$ 时，$|x-b_i|$ 符号由负转正，对应函数的斜率为 $-2*n+p+4*i$ 。 $x>b_{n}$ 时，$|x-b_n|$ 符号由负转正，对应函数的斜率为 $-2*n+p+4*n=p+2*n$ 。 我们要找的最低点，就是斜率恰好由负转正（或者0）的拐点。 ------------ 分几种情况讨论： 如果一开始的斜率 $-2*n+p<=0$ 那么最低点会延伸到 $-\infty$ ，输出No。 如果最后的斜率 $2*n+p<0$ 那么最低点会延伸到 $+\infty$ ，输出No。 其余情况，令 $-2*n+p+4*i=0$ 得 $i=\frac{2*n-p}{4}

若 4\mid (2*n-p)，i=\frac{2*n-p}{4} ，在 x<b_i 时斜率为负数，在 b_i\le x\le b_{i+1} 时斜率为 0，答案即为 b_i 。

若 4\nmid(2*n-p)，i=\lfloor \frac{2*n-p}{4}\rfloor ，在 x<b_i 时斜率为负数，在 x>b_{i+1} 时斜率为正数，答案即为 b_i 。

综上，除了两种No的情况，答案为第 \lfloor \frac{2*n-p}{4}\rfloor 小的数。

但在n为1e6级别，要做到O（n）求解，可见第k小的数模板。

如果O（nlogn）求解只能55分 别问我怎么知道的

#include<bits/stdc++.h>
using namespace std; 
int t,n,p,a[1000001],k;
int main()
{   scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&p);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        if(abs(p)>2*n||2*n==p) printf("No\n");//延伸到无穷的两种情况 输出No
        else{k=(2*n-p+3)/4;//+3等价于向下取整
            nth_element(a+1,a+k,a+n+1);
            printf("%d\n",a[k]);//第k小的数
        }
    }
    return 0;
}