2020年牛客算法入门课练习赛1(ABDE)

咕咕咕~

A. 第k小数 （快排，STL之nth_element）

题意：

给定一个序列，求第k小数的值。

思路：

1.会把sort卡掉，可以用快速排序的思想来做。

2 .C++的STL里有一个 nth_element ，可以线性寻找第k小数，get了。

代码：

1 . https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43822588

2 .

const int maxn=5e6+100;
int a[maxn],n;

int main(){
   int T=read();
    while(T--){
        int n,k;
        n=read(),k=read();
        for(int i=1;i<=n;i++) a[i]=read();
        nth_element(a+1,a+k,a+1+n);
        cout<<a[k]<<endl;
    }
    return 0;
}

B. 不平行的直线 （STL之set）

题意：

n个点，两两可以成为一个直线，问最多能够选出多少条直线使得他们不平行也不重合。

思路：

两层for循环枚举求出斜率，用set存一下，最后输出set的大小。

要注意斜率不存在的情况，可以假设等于一个特殊的数字。

因为x,y的范围都是-1000~1000，所以斜率为10000的情况是不会出现的，可以假设斜率不存在时的斜率为10000；

代码：

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43859895

C.丢手绢（三分，尺取）

题意：

给一个圆圈，给定相邻两点间的距离，定义不相邻两点之间的距离为 沿着圆圈顺时针走或者逆时针走的最近距离。 求两点的最远距离。

思路：

直接放巨巨题解啦

D.二分（差分）

题意：

猜数游戏，如果猜的数字大于答案，就输出“+”；如果猜的数字小于答案，就输出“-”；如果等于答案，就输出“.”，给出n个回答，问最多有多少条回答可以同时正确。

思路：

考虑每个回答x对答案的贡献。

如果是+，说明该回答对[-inf,x-1]的数都有贡献；

如果是-，说明该回答对[x+1,inf]的数都有贡献；

如果是.，说明该回答对x这个数做出了贡献;

然后就可以前缀和求一个被覆盖最多的数了。

因为数据很大，可以离散化一下，也可以直接用map来存。

然后inf必须是int的最大值，0x3f3f3f3f是过不去的。

代码：

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43860083

E.交换

题意：

求最少交换多少次才能使数组从小到大有序。

思路：

本来以为是个求逆序对结果死活过不去0.0

然后卑微看完了所有题解，终于在Aarynon巨巨的图解说明下懂得了

因为是可以任意选两个数交换，结合一下巨巨的图解，对于每一个环，交换次数就是环长度-1，最后答案就是所有环的长度之和-环的个数,即n-环的个数。

代码：

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43860226