　　题目传送门

取数

题目描述

在一个n行m列的数阵中，你须在每一行取一个数（共n个数），并将它们相加得到一个和。对于给定的数阵，请你输出和前k小的取数方法。

输入输出格式

输入格式：

第一行，三个数n,m,k。

第2~n+1行，每行m个正整数

输出格式：

一行共k个数，代表在每一行取一个数前k小的加和

输入输出样例

输入样例#1：复制

输出样例#1：复制

5 6

说明

对于20%的数据，n≤8

对于100%的数据，n≤800，k≤m≤800

　　分析：

　　WA了无数次，最后发现就是一个取址符号没打。。。。。。真煞笔。。。

　　这个蒟蒻真的懒得写了，如果想看思路就参考一下这里吧，蒟蒻就只上代码了。

　　Code：

#include<bits/stdc++.h>

using namespace std;

int n,m,k,a[][];

int size,b[],c,cc;

struct Node{

    int x,y,num;

}bdg,h[];

inline void Swap(Node &x,Node &y)

{Node temp=x;x=y;y=temp;}

inline void ins(Node x)

{

    h[++size]=x;

    int ka=size;

    while(ka>){

        if(h[ka].num<h[ka>>].num){

        Swap(h[ka],h[ka>>]);ka>>=;}

        else break;}

}

inline void delet()

{

    h[]=h[size--];

    int ka=,s=ka<<;

    while(s<=size){

        if(s<size&&h[s+].num<h[s].num)s++;

        if(h[s].num<h[ka].num){

        Swap(h[s],h[ka]);ka=s;s=ka<<;}

        else break;}

}

inline Node get()

{

    Node ret=h[];

    delet();return ret;

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    for(int i=;i<=m;i++)

    scanf("%d",&a[c][i]);

    sort(a[c]+,a[c]+m+);

    for(int j=;j<=n;j++){

        cc=-c;size=;

        for(int i=;i<=m;i++)

        scanf("%d",&b[i]);

        sort(b+,b+m+);

        bdg.x=;

        for(int i=;i<=k;i++){

            bdg.y=i;bdg.num=a[c][]+b[i];ins(bdg);}

        for(int i=;i<=k;i++){

            bdg=get();

            a[cc][i]=bdg.num;

            bdg.x++;bdg.num=a[c][bdg.x]+b[bdg.y];

            ins(bdg);}

        c=-c;}

    for(int i=;i<=k;i++)

    printf("%d ",a[c][i]);

    return ;

}

巴特西

洛谷P1392 取数 [堆]

取数

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章