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

A.第k小数

开始题目的数据范围给错了，本菜鸡也是只会sort排序，没过,一想，直接用下桶排序试试，还过了，数据有点水，a的范围说是int，其实没有。后来补题的时候看大佬用了nth_element( a , a + k-1, a + n ); 就是直接找一个第k小的数放到a[k-1]的位置，保证0~k-2的数据比a[k-1]小，右边的比a[k-1]大。（下标从0开始）

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
const ll MOD = 1e5 + 7;
const ll maxn =5e6+7;
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]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
ll a[maxn];
int main(){
    int T=read();
    while(T--){
      int n=read(),k=read();
        for(int i=0;i<n;i++)
            a[i]=read();
        nth_element( a , a + k-1, a + n  );
        cout<<a[k-1]<<endl;
    }
}

E.交换

戳我传送

算法思想：
1.这里的交换和冒泡的不一样，小朋友不用必须相邻也能交换。
2.假如有n个小朋友，考虑最多的交换次数，则有n次，这种情况是一次交换只能是一个小朋友有序。
3.接下来就是特殊的情况，就是比较交换前后的位置变化，这里我们可以用一个pair来记录位置。比如 3 2 1 下标分别为 1 2 3.排序后为 1 2 3. 这里可以看出是 1 和 3 交换了。我们可以从头开始遍历，也就是1到3的位置，3到1的位置，1-3-1是一个环，里面有两个元素，交换次数为2-1==1.对n元的环也一样，交换的次数为n-1。
4.也就是说有一个环，交换的次数就减一。最后的交换次数为n-环的个数。

#include <iostream>
#include<bits/stdc++.h>
#include<algorithm>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
const ll MOD = 1e5 + 7;
const ll maxn =1e5+7;
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]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a; b >>= 1; a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
ll visited[maxn];
pair<ll,ll>a[maxn];
int main(){
   int n=read();
   for(int i=1;i<=n;i++){
       a[i].first=read();
       a[i].second=i;
   }
   sort(a+1,a+n+1);
   ll ans=0;
   for(int i=1;i<=n;i++){
       if(visited[a[i].second]) continue;
       auto it=a[i];
       while(!visited[it.second]){
           visited[it.second]=1;
           it=a[it.second];//转到它原先的位置上的点，即和它交换的点
       }
       ans++;
   }
   cout<<n-ans<<endl;
}