A 第K小数

链接：https://ac.nowcoder.com/acm/contest/5773/A
题意：
找到从小到大排好序后的第K个数
题解：
用快读+sort排序就好了
注意：
数据范围是5e6
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a[5000005];

inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        memset(a,0,sizeof(a));
        int s,t;
        s=read();
        t=read();
        for(int i=0;i<s;i++)
        {
            a[i]=read();
        }
        sort(a,a+s);
        printf("%d\n",a[t-1]);
    }
    return 0;
}

B 不平行的直线

链接：https://ac.nowcoder.com/acm/contest/5773/B
题意：
找到两点连接形成的不同直线的个数
题解：
直线平行或者重合都是由直线的斜率决定，也就是说，直线的条数即为斜率K的个数。其中斜率的求法(y2-y1)/(x2-x1)。暴力求出所有的k，用stl中的set来记录就好了。因为set函数能够自动去重，.size（）函数直接计算k的个数。
注意：
注意k值为无穷（x1==x2）的时候要分情况考虑
还有斜率是小数,所以要用double类型
代码：

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
struct node{
    double x;double y;
}mark[205];
int main()
{
    set<double>KKK;
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lf%lf",&mark[i].x,&mark[i].y);
    }
    int s=0;
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(mark[i].x==mark[j].x)s=1;
            else {
                KKK.insert((mark[i].y-mark[j].y)/(mark[i].x-mark[j].x));
            }
        }
    }
    printf("%d",KKK.size()+s);
    return 0;
}

E 交换

链接：https://ac.nowcoder.com/acm/contest/5773/E
题意：
任意两个人之间的次序可以进行交换，为使数列有序，求交换的最少次数
题解：
先将数列排好序存起来，再将这个数列与原先的数列进行一个对照。找到循环节的个数。而循环节里面的个数-1就是需要交换的次数。将所有不能一一对应的数个数统计出来-循环节的个数就好了。

注意:
可以用map来找编号,for的话会T。
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a[100009];
int b[100009];
int flag[100009];
#include<map>
int main()
{
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(flag,0,sizeof(flag));
    map<int,int>m;
    int n;int j=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
    {
        m[b[i]]=i;
    }
    int y=0;int s=0;
    for(int i=1;i<=n;i++)
    {
        if(b[i]==a[i])continue;
        s++;
        if(flag[i]==1)continue;
        int x=a[i];
        while(x!=b[i])
        {
            int j=m[x];
            x=a[j];
            flag[j]=1;
        }
        y++;
    }
    printf("%d\n",s-y);
    return 0;
}