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

A 第K小数

题目描述：

给你一个长度为n的序列，求序列中第k小数的多少。

思路：

因为数字比较小，用桶排序，可以做到O(n)

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=5e6+10;
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 t;
int a[N];
int gs[N];
int main()
{
    scanf("%d",&t);
    while(t--) {
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++) gs[i]=0;
        for(int i=1;i<=n;i++) {
            a[i]=read();
            gs[a[i]]++;
        }   
        int pos=1,ans=1;
        while(k) {
            if(gs[pos]<k) {
                k-=gs[pos];
                pos++;
            }else {
                ans=pos;
                k=0;
            }
        }
        printf("%d\n",ans);
    }

}

B 不平行的直线

题目描述：

$n$ 个点，两两形成一条直线，问最多有多少条不平行且不重合的直线

思路：

使用 $set$ 去重即可，对于一条直线直接保存斜率的分子分母 $(x,y)$ ，化成最简并且 $x$ 同号即可，时间复杂度 $O(n^2log)$

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=500;
int gcd(int a,int b) {
    return b==0?a:gcd(b,a%b);
}
int x[N],y[N];
set<pair<int,int> >s;
void cl(int a,int b) {
    int X=x[a]-x[b];
    int Y=y[a]-y[b];
    int g=gcd(X,Y);
    X/=g;
    Y/=g;
    if(X<0) X*=-1,Y*=-1;
    s.insert(make_pair(X,Y));
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d%d",&x[i],&y[i]);
    }
    for(int i=1;i<=n;i++) {
        for(int j=i+1;j<=n;j++) {
            cl(i,j);
        }
    }
    printf("%d\n",int(s.size()));
}

C 丢手绢

题目描述：

$n$ 个人，围成一圈，已知相邻人的距离，求最远的两个人的距离

思路：

预处理顺时针距离前缀和，可以 $O(1)$ 求出两个人之间的最短距离，逆时针用总长减去顺时针即可。然后使用尺取法的思想，对于第 $i$ 个人找到离他最远的 $j$ ，那么对于 $i+1$ 来说离他最远的一定大于 $j$ ，那么就可以 $O(n)$ 的时间解决了。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int d[N];
int sum[N];
int n;
int R;
int dis(int x,int y) {
    return sum[y-1]-sum[x-1];
}
int js(int x,int y) {
    return min(dis(x,y),R-dis(x,y));
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&d[i]);
        R+=d[i];
    }
    for(int i=1;i<=n+1;i++) {
        sum[i]=sum[i-1]+d[i];
    }
    int j=2;
    int ans=0;
    for(int i=1;i<=n;i++) {
        while(j<n&&js(i,j)<=js(i,j+1)) {
            j++;
        }
        //cout<<i<<" "<<j<<endl;
        ans=max(ans,js(i,j));
    }
    printf("%d\n",ans);
}

D 二分

题目描述：

裁判有一个数字 $x$ ， $n$ 次询问，每一次猜一个数字，返回3种结果， $. + -$ 分别代表猜对了，猜的大了，猜的小了。问最多有多少个返回结果同时合法。

思路：

可以枚举数字 $x$ 的值，我们将每次猜的数字和加一、减一都保存下到 $v$ 数组，可以发现，其中必然存在一个数字可以作为 $x$ 并且是结果最大。所以枚举数组里的值即可。

假设每次查询数字 $x$ ，那么合法的结果个数就是下面三种情况个数的和。

返回 . 的等于 $x$ 的个数

返回 + 的大于 $x$ 的个数

返回 - 的小于 $x$ 的个数

取最大值即可。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>v1,v2,v3;
vector<int>v;
int n;
int js(int x) {
    int p1,p2;
    int ans=0;
    p1=lower_bound(v1.begin(),v1.end(),x)-v1.begin();
    p2=upper_bound(v1.begin(),v1.end(),x)-v1.begin();
    ans+=p2-p1;
    p1=upper_bound(v2.begin(),v2.end(),x)-v2.begin();
    p2=v2.size();
    ans+=p2-p1;
    p1=lower_bound(v3.begin(),v3.end(),x)-v3.begin();
    ans+=p1;
    return ans;
}
int main() {
    scanf("%d",&n);
    char c;
    int x;
    for(int i=1;i<=n;i++) {
        scanf("%d %c",&x,&c);
        if(c=='.') v1.push_back(x);
        if(c=='+') v2.push_back(x);
        if(c=='-') v3.push_back(x);
        v.push_back(x+1);
        v.push_back(x);
        v.push_back(x-1);
    }
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    sort(v3.begin(),v3.end());
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    int ans=0;
    for(int a:v) {
        ans=max(ans,js(a));
    }
    printf("%d\n",ans);
}

E 交换

题目描述：

n个数字，要求从小到大排列，问最少交换两个数字几次。

思路：

可以发现，对于一个 $a->b->c->a$ 这种的类型的交换，需要的是点个数-1次交换，那么对于这个序列来说，我们只要计算出所有这种类型的交换集，然后答案就是总点数-交换集的个数。

对于该问题，可以转化成图论来解决，即求环的个数。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int a[N],b[N];
bool vis[N];
vector<int>v;
int getid(int x) {
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
vector<int>e[N];
void dfs(int u) {
    vis[u]=1;
    for(int a:e[u]) {
        if(!vis[a]) {
            dfs(a);
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        v.push_back(a[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;i++) {
        b[i]=getid(a[i]);
    }
    for(int i=1;i<=n;i++) {
        e[i].push_back(b[i]);
    }
    int ans=0;
    for(int i=1;i<=n;i++) {
        if(!vis[i]) {
            ans++;
            dfs(i);
        }
    }
    printf("%d\n",n-ans);
}