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

Powered by:AB_IN 局外人

A 第k小数

nth_element(a+1,a+k,a+n+1)

则

a[k]

为第k小整数。注意不！去！重！

用sort会卡t哦。

#include<bits/stdc++.h>
typedef long long ll;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
const ll maxn=1e7+10;
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; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
ll t,n,k,a[maxn];
int main()
{
    t=read();
    while(t--){
        memset(a,0,sizeof(a));
        n=read();k=read();
        for(int i=1;i<=n;i++)
            a[i]=read();
        nth_element(a+1,a+k,a+n+1);
        write(a[k]);putchar(10);
    }
}
           

注：第k小整数(与上面一题类似)

B 不平行的直线

就是统计有多少种不同的斜率就行了，要是横坐标相等，就放进去最大值。

#include<bits/stdc++.h>
typedef long long ll;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
const ll maxn=2e6+10;
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; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[200]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
ll t,x[maxn],y[maxn];
set<double>s;
int main(){
    t=read();
    for(int i=1;i<=t;i++)
        x[i]=read(),y[i]=read();
    for(int i=1;i<t;i++){
        for(int j=i+1;j<=t;j++){
            if(x[i]==x[j])
                s.insert(0x3f3f3f3f);
            else
                s.insert(double(y[i]-y[j])/double(x[i]-x[j]));
        }
    }
    write(s.size());
}
           

E 交换

网上找的模版，以后套模版就好了。[doge]

题意：最少需要自由交换多少次，使数组从小到大排序。

涉及到循环节的问题。

#include<bits/stdc++.h>
using namespace std;
int getMinSwaps(vector<int> &nums){
    //排序
    vector<int> nums1(nums);
    sort(nums1.begin(),nums1.end());
    map<int,int> m;
    int len = nums.size();
    for (int i = 0; i < len; i++){
        m[nums1[i]] = i;//建立每个元素与其应放位置的映射关系
    }
    int loops = 0;//循环节个数
    vector<bool> flag(len,false);
    //找出循环节的个数
    for (int i = 0; i < len; i++){
        if (!flag[i]){//已经访问过的位置不再访问
            int j = i;
            while (!flag[j]){
                flag[j] = true;
                j = m[nums[j]];//原序列中j位置的元素在有序序列中的位置
            }
            loops++;
        }
    }
    return len - loops;
}
int n,x;
int main()
{
    vector<int>vis;
    cin>>n;
    while(n--){
        cin>>x;
        vis.push_back(x);
    }
    int ans=getMinSwaps(vis);
    cout<<ans;
    return 0;
}
           

那么…如果只能相邻交换呢？

即求逆序数！传送门

PS:一篇挺好的题解！(有只交换相邻的，和自由交换的)

你问菜鸡又学到了什么？ …没错。

巨快读

一般在循环读入用，读一次的还是

scanf

快点。

输出用

printf

。

char buf[1 << 21], *p1=buf, *p2=buf;
inline ll getc(){
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
inline ll read() {
    ll ret = 0,f = 0;char ch = getc();
    while (!isdigit (ch)) {
        if (ch == '-') f = 1;
        ch = getc();
    }
    while (isdigit (ch)) {
        ret = ret * 10 + ch - 48;
        ch = getc();
    }
    return f ? -ret : ret;
}
           

所以…

A的改进版！！

#include<bits/stdc++.h>
typedef long long ll;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
const ll maxn=5e6+10;
char buf[1 << 21], *p1=buf, *p2=buf;
inline ll getc(){
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
inline ll read() {
    ll ret = 0,f = 0;char ch = getc();
    while (!isdigit (ch)) {
        if (ch == '-') f = 1;
        ch = getc();
    }
    while (isdigit (ch)) {
        ret = ret * 10 + ch - 48;
        ch = getc();
    }
    return f ? -ret : ret;
}
ll t,n,k,a[maxn];
int main()
{
    scanf("%lld",&t);
    while(t--){
        n=read();k=read();
        for(int i=1;i<=n;i++)
            a[i]=read();
        nth_element(a+1,a+k,a+n+1);
        printf("%lld\n",a[k]);
    }
}
           

完结。