题目描述

输入一个长度为n的整数数列，从小到大输出前m小的数。

输入格式
第一行包含整数n和m。

第二行包含n个整数，表示整数数列。

输出格式
共一行，包含m个整数，表示整数数列中前m小的数。

数据范围
1≤m≤n≤10^5,
1≤数列中元素≤10^9

样例

输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3

算法1

( sort(光速逃 ) $O(nlogn)$

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,a[100005];
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=m;i++)
    cout<<a[i]<<' ';
}

算法2

(纯down操作)

参考文献

y总代码

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,h[N],cnt;
void down(int u)
{
    int t=u;
    if(u*2<=cnt&&h[u*2]<h[t])
    t=u*2;
    if(u*2+1<=cnt&&h[u*2+1]<h[t])
    t=u*2+1;
    if(u!=t)
    {swap(h[u],h[t]);
    down(t);}
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&h[i]);
    cnt=n;
    for(int i=n/2;i;i--)
    down(i);
    while(m--)
    {
    printf("%d ",h[1]);
    h[1]=h[cnt--];
    down(1);
    }
    puts("");
    return 0;
}

算法3

(down+up操作)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n,a[100005],k,s,si;
void down(int x)
{
    int t=x;
    if(x*2<=si&&a[x*2]<a[t])
    t=x*2;
    if(x*2+1<=si&&a[x*2+1]<a[t])
    t=x*2+1;
    if(x!=t)
    {swap(a[x],a[t]);
    down(t);}
}
void up(int x)
{
    s=x;
    while(s!=1)
    {
    if(a[s]<a[s/2])
    {swap(a[s],a[s/2]);
    s/=2;}
else break;
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {cin>>s;
    a[++si]=s;
    up(si);}
    for(int i=1;i<=k;i++)
    {
    cout<<a[1]<<' ';
    swap(a[1],a[si]);
    si--;
    down(1);
    }
}

#include<bits/stdc++.h>
using namespace std;
struct ss
{
    int u,v,w;
}a[800005];
inline bool cmp(ss a,ss b){return a.w<b.w;}
int n,m,d[400005],ans;
inline int afind(int x)
{
    if(x==d[x])
    return x;
    return d[x]=afind(d[x]);
}
inline int kruskal()
{
    int vv,uu,sum=0;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
    vv=afind(a[i].v);
    uu=afind(a[i].u);
    if(vv==uu)
    continue;
    sum+=a[i].w;
    d[uu]=vv;
    if(++ans==n-1)
    break;
    }
    if(ans==n-1)
    return sum;
    return 2e9;
}
int main()
{
    int t;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    d[i]=i;
    for(int i=1;i<=m;i++)
    cin>>a[i].u>>a[i].v>>a[i].w;
    t=kruskal();
    if(t!=2e9)
    cout<<t<<endl;
else puts("impossible");
}

#include <bits/stdc++.h>
using namespace std;
int s1=1,s2=1,a[100005],n,m,b[100005];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=m;i++)
    cin>>b[i];
    while(s1<n&&s2<m)
    {if(a[s1]==b[s2])s1++;
    s2++;}
    if(s1==n)
    puts("Yes");
else puts("No");
}

#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005],n,m,s,lena,lenb,ans;
char a[1005][15],b[15];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%s",a[i]+1);
    while(m--)
    {
    scanf("%s%d",b+1,&s);
    lenb=strlen(b+1);
    ans=0;
    for(int i=1;i<=n;i++)
    {
    lena=strlen(a[i]+1);
    for(int j=0;j<=lenb;j++)
    dp[0][j]=j;
    for(int j=0;j<=lena;j++)
    dp[j][0]=j;
    for(int j=1;j<=lena;j++)
    for(int k=1;k<=lenb;k++)
    {
    dp[j][k]=min(dp[j-1][k]+1,dp[j][k-1]+1);
    if(a[i][j]==b[k])
    dp[j][k]=min(dp[j][k],dp[j-1][k-1]);
else dp[j][k]=min(dp[j][k],dp[j-1][k-1]+1);
    }
    if(dp[lena][lenb]<=s)
    ans++;
    }
    cout<<ans<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
inline long long gsj(long long a,long long b,long long p)
{
    long long ans=0;
    while(b)
    {
    if(b&1)
    ans=(ans+a)%p;
    a=(a+a)%p;
    b=b>>1;
    }
    return ans;
}
int main()
{
    long long a,b,p;
    scanf("%lld%lld%lld",&a,&b,&p);
    printf("%lld",gsj(a,b,p));
}

#include <bits/stdc++.h>
using namespace std;
int t,n,m,a[105][105],dp[105][105];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
    memset(a,0,sizeof(a));
    memset(dp,0,sizeof(dp));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    dp[i][j]=max(dp[i-1][j]+a[i][j],dp[i][j-1]+a[i][j]);
    printf("%d\n",dp[n][m]);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
long long a,b,x,y;
int gcd(long long a,long long b,long long &x,long long &y)
{
    if(!b)
    {x=1;
    y=0;
    return a;}
    int d=gcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main()
{
    cin>>a>>b;
    gcd(a,b,x,y);
    cout<<(x%b+b)%b;
}

#include <bits/stdc++.h>
#define re register int
using namespace std;
int a[1000005];
bool v[1000005];
int main()
{
    re s=-1,n,flag;
    for(re i=2;i<=1000000;i++)
    if(!v[i])
    {a[++s]=i;
    for(re j=i+i;j<=1000000;j+=i)
    v[j]=1;
    }
    while(cin>>n&&n)
    {
    flag=0;
    for(re i=1;i<=n;i++)
    {if(a[i]>n)
    break;
    if(!v[n-a[i]])
    {flag=1;
    printf("%d = %d + %d\n",n,a[i],n-a[i]);
    break;}
    }
    if(!flag)
    printf("Goldbach's conjecture is wrong.\n");
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
int n,a,sum;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {scanf("%d",&a);
    q.push(a);}
    for(int i=1;i<n;i++)
    {
    sum+=q.top();
    a=q.top();
    q.pop();
    sum+=q.top();
    a+=q.top();
    q.pop();
    q.push(a);
    }
    printf("%d",sum);
}