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

A.第k小数

大致题意：多组输入，求序列中的第k小数。
$图片说明$

分析：两种解法，一个是快速排序求第k小，一个是STL自带的nth_element函数，O(n)求第k小的.

快排求第k小......

#include<bits/stdc++.h>
using namespace std;

 const int maxn=5e6+10;
int arr[maxn];


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;
}


void quickSelect( int a[],int l,int r,int rk )
{
    int i=l,j=r;
    int mid=a[l+r>>1];
    do{
        while( a[i]<mid ) ++i;
        while( a[j]>mid ) --j;
        if(i<=j ) swap(a[i],a[j]),++i,--j; 
    }while( i<=j );
    if( l<=j && rk<=j-l+1 ) quickSelect(a,l,j,rk);
    if( i<=r && rk>=i-l+1 ) quickSelect(a,i,r,rk-(i-l));
}

int quick_select( int a[],int n,int k )
{
    quickSelect(a,1,n,k);
    return a[k];
}

int main()
{

    int t=read();
    while( t-- )
    {
        int n=read(),k=read();
        for(int i=1;i<=n;++i) arr[i]=read();
        printf("%d\n",quick_select(arr,n,k));
    }
}

nth_element函数

#include<bits/stdc++.h>
using namespace std;

 const int maxn=5e6+10;
int arr[maxn];


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 main()
{

    int t=read();
    while( t-- )
    {
        int n=read(),k=read();
        for(int i=1;i<=n;++i) arr[i]=read();
        nth_element(arr+1,arr+k,arr+1+n);
        printf("%d\n",arr[k]);
    }
}

B.不平行的直线

~~比赛一直以为是求两两相交的直线有多少条，写完发现样例都不对，.......~~
大致题意: 求n个点可以两两连成的所有直线，选出尽可能多的直线满足两两不平行也不重合。
$图片说明$

分析: 直接用pair<int,int> 存直线向量(当然要化简),对于平行于坐标轴的向量直接赋为(1,0)或者(0,1).最后可以用map计算出现的不同直线向量个数.(这样存储，不用考虑精度问题

#include<bits/stdc++.h>
using namespace std;

const int maxn=40005;

map< pair<int,int>,int > mp;

int x[maxn],y[maxn];

int main()
{
    int n;
    cin>>n;
    for( int i=1;i<=n;i++ )
    {
        cin>>x[i]>>y[i];
    }
    int all=0;
    for( int i=1;i<=n;i++ )
    {
        for( int j=i+1;j<=n;j++ )
        {
            int dx=x[j]-x[i],dy=y[j]-y[i];
            if( dx==0 && dy==0 ) continue;
            if( dy && dx )
            {
                int gd=__gcd(dx,dy);
                dx/=gd;
                dy/=gd;
            }
            if( dx<0 )   dx*=-1,dy*=-1;
            if( dx==0 && dy )  dy=1;
            if( dy==0 && dx ) dx=1;
            pair<int,int> tmp=make_pair(dx,dy);
            mp[tmp]++;
            all++;
        }
    }
    int ans=0;
    for( auto v:mp )   
    {
        ans++;
    }
    cout<<ans<<endl;
}

D.丢手绢

题意：n个人围成一个圈，给定相邻每个人的距离，问n个人中两人最远距离是多少。(距离都是绕圆弧计算的)

$图片说明$ .

分析：两种解法：尺取法O(n)和三分O(nlogn).

尺取法：我们枚举点i从1到n,初始化点j=2,然后每次计算i到j的最短距离 $图片说明$ ,和i到j+1的最短距离 $图片说明$ ,
如果 $图片说明$ 明显对于j而言到(i+1 ~~ n)点的距离一定是比 $图片说明$ 小的(自行画图易得)，那么我们更新下可以直接让j++,跳到下一个点更新。
求解两点之间的距离，我们可以顺时针维护前缀和，两点间的距离就是区间和。由于是个圆，两个点的距离是逆时针的距离，那么求 $图片说明$ 就是两种距离取最小值。

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;

int sum[maxn],a[maxn];
int c;
int dis( int x,int y ) { return sum[y-1]-sum[x-1]; }
int mins( int x,int y ) { return min(dis(x,y),c-dis(x,y)); }

int main()
{
    int n;
    cin>>n;
    for( int i=1;i<=n;i++ ) cin>>a[i],sum[i]=sum[i-1]+a[i];
    c=sum[n];
    int j=2,ans=0;
    for( int i=1;i<=n;i++ )
    {
        while( j<n && mins(i,j)<=mins(i,j+1) ) j++;
        ans=max(ans,mins(i,j) );
    }
    cout<<ans<<endl;
}

三分: 从尺取法我们可以发现对于i点而已，在其他点中存在一个j点离i点最近，并且所有点与i点的距离是一个凸函数。我们可以用三分求最远距离的那个j点，进行更新答案.

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;

int sum[maxn],a[maxn];
int c;
int dis( int x,int y ) { return sum[y-1]-sum[x-1]; }
int mins( int x,int y ) { if( x>y ) swap(x,y); return min(dis(x,y),c-dis(x,y)); }

int main()
{
    int n;
    cin>>n;
    for( int i=1;i<=n;i++ ) cin>>a[i],sum[i]=sum[i-1]+a[i];
    c=sum[n];
    int j=2,ans=0;
    for( int i=1;i<=n;i++ )
    {
//      while( j<n && mins(i,j)<=mins(i,j+1) ) j++;
//      ans=max(ans,mins(i,j) );
        int l=1,r=n,res=0;
        while( r-l>5 )
        {
            int mid1=(r-l)/3+l,mid2=mid1+(r-l)/3;
            if( mins(i,mid1)<mins(i,mid2) ) l=mid1,res=mins(i,mid2);
            else r=mid2,res=mins(i,mid1);  
        }
        if( r-l<=5 ) for( int j=l;j<=r;j++ ) res=max(res,mins(i,j));
        ans=max(ans,res);
    }
    cout<<ans<<endl;
}

D.二分

大致题意：一个猜数游戏，有n次猜数(pos,s).
s为'.'的时候表示正确数字就是猜的数字pos.
s为'+'的时候表示猜的数字pos比正确的数字大.
s为'-'时候候表示猜的数字pos比正确的数字小.
n次猜数不一定都是对的。
求正确数字为多少的时候，满足最多猜数是正确的。 $图片说明$

分析：我们可以用差分解此题，每次猜数可以知道当前合法正确答案的区间是多少.
s='.' ，a[pos]++,a[pos+1]--.
s='-',a[pos+1]++,a[inf]--.
s='+'，a[-inf]--,a[pos]++.
由于数据范围比较大，我们可以用map实现或者用结构体存储边界标记，排序后依次遍历每个边界位置求取答案.

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;
const int inf=INT_MAX;

map<int,int> mp;

int main()
{
    int n;
    cin>>n;
    int cnt=0;
    for( int i=1;i<=n;i++ )
    {
        int x,l,r;char s;
        cin>>x>>s;
        if( s=='.' ) mp[x]++,mp[x+1]--;
        else if( s=='+' ) mp[-inf]++,mp[x]--;
        else if( s=='-' ) mp[x+1]++,mp[inf]--;
    }
    int sum=0,ans=0;
    for(auto v:mp )
    {
        sum+=v.second;
        ans=max(ans,sum);
    }
    cout<<ans<<endl;

}

E.交换

~~一直看成只能换相邻位置元素，吐了....~~
题目大意：给定一个序列，可以任意交换两个元素，问使得序列变成升序，交换次数是多少.
分析：

我们考虑每一次交换可以使得一个元素到排序后对应位置(暂不考虑一次交换可以使得两个元素到对应位置)，那么总的交换次数是n次。
但是举个简单的例子2 2 1, 我们只用交换一次就可以使得序列有序。初始序列元素2 占了元素1 该有的位置，元素1 占了元素2 该有的位置，这个形成了一个环，对于环上的元素，假如环上元素共有x个,我们只用交换x-1次便可以让环上的元素到达自己的对应位置.那么相当于一个环可以让交换次数减一，那么答案就是n-环的个数。(当然初始位置和排序位置相同的元素自己构成了自环）。

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;

pair<int,int> p[maxn];
bool vis[maxn];

int main()
{
    int n;
    cin>>n;
    for( int i=1;i<=n;i++ )
    {
        int x;cin>>x;
        p[i].first=x;
        p[i].second=i;
    }
    sort(p+1,p+1+n);
    int ans=0;
    for( int i=1;i<=n;i++ )
    {
        if( vis[i] ) continue;
         pair<int,int> tmp=p[i];
        while( !vis[tmp.second] )
        {
            vis[tmp.second]=true;
            tmp=p[tmp.second];
        }
        ans++;
    }
    cout<<n-ans<<endl;
}