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

前面的话：由于菜鸡实力有限+粗心，可能出现诸多错误或者是难以理解的地方，欢迎各位大佬指出，非常感谢

A 第k大数

可惜sort会被卡。（但是有欧皇这样过了）
一开始想写分治，也可惜我太菜了没写出来。
然后桶排偷鸡过了（数据太弱没测出来，按道理应该会卡的。基排也可以
之后知道了这么好用的一函数：nth_element作用为求第n大的元素，并把它放在第n位置上，下标是从0开始计数的，也就是说求第0小的元素就是最小的数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const ll maxn=1e7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int a[maxn];
int main() {
    ll T = read();
    while ( T-- ) {
        ll n = read(), k = read();
        for(int i=0; i<n; ++i) a[i] = read();
        nth_element( a + 1, a + k, a + n + 1 );
        cout<<a[k]<<endl;
    }
    return(0);
}

B 不平行的直线

用set来存斜率。
如果斜率不存在，随便用个max来记录。
最后输出set中元素个数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const double maxn=1e7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
set<double>s;
int x[205],y[205];
int main() {
    ll n = read();
    ll x[205], y[205];
    for (int i = 0; i < n; ++i) x[i] = read(), y[i] = read();
    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j)
            if (x[i] == x[j])
                s.insert(maxn);
            else
                s.insert(double((y[i] - y[j])) / (x[i] - x[j]));
    cout<<s.size()<<endl;
    return 0;
}

C 丢手绢

前缀和尺取
这样就知道了每一个点的顺时针距离，然后对每个点搜索找到最大距离

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const ll maxn=1e7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int a[100005];
int main() {
    ll n=read(),max=0;
    for(int i=1;i<=n;++i)
        a[i]=read(),a[i]+=a[i-1];

    for(int i=0;i<n;++i){
        for(int j=i;j<n;++j){
            int tmp=a[j]-a[i];
            if(a[j]-a[i]==a[n]/2) {
                printf("%d\n",a[n]/2);
                return 0;
            }
            else if((a[j]-a[i])>(a[n]/2) && (a[n]-a[j]+a[i])>max) max=a[n]-a[j]+a[i];
            else if((a[j]-a[i])<(a[n]/2) && (a[j]-a[i])>max) max=a[j]-a[i];
        }
    }
    printf("%d\n",max);
}

D 二分

参考了大佬代码
枚举所有数判断最多的符合条件的
离散+差分
map来存数据

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const ll maxn=1e7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
const int inf=INT_MAX;
map<int,int>a;
int main() {
    ll n=read();
    char c;
    int tmp;
    for(int i=0; i<n; ++i) {
        cin>>tmp>>c;
        if(c=='.') a[tmp]++,a[tmp+1]--;
        else if(c=='+') a[tmp]--,a[-inf]++;
        else if(c=='-') a[inf]--,a[tmp+1]++;
    }
    int ans=-inf;
    tmp=0;
    for(map<int,int>::iterator it=a.begin();it!=a.end();++it) {
        tmp+=it->second;
        ans=max(tmp,ans);
    }
    cout<<ans;
}

E 交换

参考了大佬代码

题意大概可理解为有一无序数组，将其两两交换变成有序的，问最少的交换次数。
于是可以将数组以有序的形式存到另一个数组中
将每个无序数与其对应的位置相连
大概可理解为 3 1 2
↓ ↓ ↓
1 2 3

这样就有 3->2->1->3的回路，回路中形成有序的最少交换次数为2
即计算回路的个数再减即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const ll maxn=1e7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int a[100005],b[100005];
bool v[100005];
int main() {
    ll n=read();
    for(int i=1;i<=n;++i) b[i]=a[i]=read();
    sort(b+1,b+n+1);
    for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
    ll ans=0;
    for(int i=1;i<=n;++i)
        if(!v[i]){
            int tmp=i;
            while(!v[tmp]) v[tmp]=1,tmp=a[tmp];
            ans++;
        }
    printf("%d\n",n-ans);
    return 0;
}