2020年牛客算法入门课练习赛1-(A-E)

记录一下5月25日的练习赛，注重基础
题目地址->https://ac.nowcoder.com/acm/contest/5773

A.第k小数

给你一个长度为n的序列，求序列中第k小数的多少。
(1≤n≤5×10^6 ,k≤n,数列里每个数都在int范围内)

快排的模板，只需要判断第k小数在哪个区间，递归的时候只需要递归一个区间即可，时间复杂度为O(n)

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

const int N = 5e6+100;

int a[N];
int n,k;

int quick_sort(int a[],int l,int r,int k)
{
    if(l>=r) return a[l];
    int i = l-1,j = r+1;
    int mid = a[l+r>>1];
    
    while(i<j)
    {
        while(a[++i] < mid);
        while(a[--j] > mid);
        if(i<j) swap(a[i],a[j]);
    }
    int sl = j-l+1;
    if(sl>=k) return quick_sort(a,l,j,k);
    return  quick_sort(a,j+1,r,k-sl);
    
}
int main()
{
    IO;
    int t;
    cin>>t;
    while(t--){
        cin>>n>>k;
        for(int i = 1;  i<=n; i++)
            cin>>a[i];
        cout<< quick_sort(a,1,n,k) <<endl;
    }
    return 0;
}

B.不平行的直线

在坐标纸上有N个不重合的点，两两可以连一个线段并延伸成直线，请问在这些直线里最多能选出多少条使得他们两两不平行也不重合。
N≤200

暴力算出所有直线的斜率，存set去重即可

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long LL;

const int N = 1e5+100;
const double inf = 1e9;
int n;
int x[N];
int y[N];
set<double> h;
int main()
{
    IO;
    cin>>n;
    for(int i = 1; i<=n; i++){
        cin>>x[i]>>y[i];
    }
        
    for(int i = 1; i<n; i++){
        for(int j = i+1; j<=n; j++){
            double up,d;
            up = y[j]-y[i];
            d = x[j]-x[i];
            if(up == 0){
                h.insert(0);
                continue;
            }
            if(d == 0){
                h.insert(inf);
                continue;
            }
            
            h.insert(up/d);
        }
    }
    
    cout<<h.size()<<endl;
    return 0;
}

C.丢手绢

“丢~ 丢 ~丢手绢，轻轻地放在小朋友的后面，大家不要告诉她，快点快点抓住她，快点快点抓住她。”
牛客幼儿园的小朋友们围成了一个圆圈准备玩丢手绢的游戏，但是小朋友们太小了，不能围成一个均匀的圆圈，即每个小朋友的间隔可能会不一致。为了大家能够愉快的玩耍，我们需要知道离得最远的两个小朋友离得有多远（如果太远的话牛老师就要来帮忙调整队形啦！）。
因为是玩丢手绢，所以小朋友只能沿着圆圈外围跑，所以我们定义两个小朋友的距离为沿着圆圈顺时针走或者逆时针走的最近距离。
(2≤N≤100000)
距离和（圆圈周长）小于等于2147483647

尺取法求最大值，另外由于是围成一个圈，而且距离对顺时针和逆时针都有效，所以可以将圆圈拉直并拓展两倍，等效成顺时针走完再走逆时针。

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long LL;

const int N = 2e5+100;

int n;
int a[N];
int sum,ans;
//solution: 尺取法
int main()
{
    IO;
    cin>>n;
    for(int i = 1; i<=n; i++){
        cin>>a[i];
        sum += a[i];
    }
    int num;
    cin>>num;
    sum /=2;
    
    for(int i = n+1; i<=2*n; i++){
        a[i] = a[i-n];
    }
    int t = 0;
    int l = 0, r = 1;
    while(r<=2*n){
        t += a[r++];
        while(t>sum){
            t -= a[++l];++
        }
        ans = max(ans,t);
    }
    cout<<ans<<endl;
    
    return 0;
}

D.二分

我们刚刚学了二分查找——所谓二分查找就是在一堆有序数里找某个符合要求的数。在学完二分查找之后如果让你玩猜数游戏（裁判选定一个目标数字，你说一个数裁判告诉你是高了还是低了直到你猜到那个数）的话，显然你会用二分的方式去猜。

但是不是每一个玩猜数游戏的人都知道二分是最好，甚至一个健忘的玩家都有可能在得到裁判回答的下一个瞬间就忘了他之前问了什么以及裁判的回答），而现在更可怕的是，这个告诉你猜的数是高还是低的裁判他也很健忘，他总是薛定谔的记得这个目标数字，也就是说他的回答有可能出错。我们已经不关心这个不靠谱的游戏本身了，我们更关心裁判这个薛定谔的记得到底有几个是记得......

现在给出这个健忘的玩家的所有猜测和裁判的所有回答，问裁判最多能有多少次是记得目标数字的，即裁判的回复是符合情况的。

输入

第一行包含一个正整数n，表示裁判的回答数（也是玩家的猜数次数）。
接下来n行，首先是猜的数，然后是一个空格，然后是一个符号。符号如果是“+”说明猜的数比答案大，“-”说明比答案小，“.”说明猜到了答案。
4
5 .
6 +
5 .
8 -

输出

包含一个正整数，为裁判最多有多少个回答是正确的。
3

对于每次猜数和裁判的判断，可以确定一个区间内所有的数都有可能，比如对于样例中(6 +)来说，[ -INT_MIN， 5] 中所有的数都有可能，那么对于每次猜数，我们可以将一个区间内所有的数都加上1，这就用到差分了，由于区间端点在这里的作用与区间内的数相同，所以我们不需要开那么大的数组(实际上也开不了),用一个map就行了。

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long LL;

const int N = 1e5+100,INF = INT_MAX;

int n;
int a;
char b;
int ans = 0;
map<int,int> h;

//solution:  差分
int main()
{
    IO;
    cin>>n;
    for(int i = 1; i<=n; i++){
        cin>>a>>b;
        if(b == '.'){
            h[a] ++;
            h[a+1]--;
        }else if(b == '+'){
            h[-INF]++;
            h[a]--;
        }else{
            h[a+1]++;
        }
    }
    int cnt = 0;
    for(auto x: h){
        cnt += x.second;
        ans = max(ans,cnt);
    }
    cout<<ans<<endl;
   
    return 0;
}

E.交换

牛客幼儿园的小朋友课间操时间需要按照学号从小到大排队，但是他们太小了只能站成一列顺序却不对，现在幼儿园的阿姨需要帮忙交换小朋友的位置让他们最终有序，阿姨希望能尽快完成交换操作，问最少需要交换多少次，才能使得小朋友们从小到大排好。
注意：每个小朋友的学号不同，但是未必连续，因为可能有小朋友请假了没有来。
N≤100000

题意就是给定一个序列，通过交换次序使序列有序的最少交换次数，如果是交换相邻顺序，那么就是求逆序对数即可，但是这里没有限制，可以随意交换，那么answer = n - 循环节个数，这里借助一篇博客里的讲解（https://blog.csdn.net/lfb637/article/details/86653121）

）

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long LL;

const int N = 1e5+100;
int n;
int a[N];
int b[N];
bool st[N];
map<int,int> h;
int main()
{
    IO;
    cin>>n;
    for(int i = 1; i<=n; i++){
        cin>>a[i];
        b[i] = a[i];
    }
    sort(b+1,b+1+n);
    for(int i = 1; i<=n; i++) h[b[i]] = i;
    int ans = 0;
    
    for(int i = 1; i<=n; i++){
        if(st[i]) continue;
        //cout<<i<<endl;
        int j = i;
        //if(a[i]==b[i])continue;
        while(!st[j]){
            st[j] = true;
            j = h[a[j]];
        }
        ans ++;
    }
    //cout<<ans<<endl;
    cout<<n-ans<<endl;
    return 0;
}