本文共 2564 字，大约阅读时间需要 8 分钟。

[洛谷P1392]取数 解题报告

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

input

3 3 2

1 2 3

6 3 5

4 1 2

output

5 6

说明

对于20%的数据，n≤8

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

这似乎是一个模板题

首先需要一个大根堆(至于为何是大根堆等会就知道了)

code:

void down(int x){
        int l = x*2;    while(l<=len)    {
            if(l
   
    
      dui[x])         {
                swap(dui[l],dui[x]);            x=l;l=x*2;        }        else break;    }}void up(int x){
        while(x>1)    {
            if(dui[x]>dui[x/2])        {
                swap(dui[x],dui[x/2]);            x/=2;        }        else break;    }}void gettop(int val){
        dui[1]=val;    down(1);}void add(int val){
        dui[++len]=val;    up(len);}
    
   

然后就是重点了。

先把第一加入堆

之后把接下来的每一行排序， 对于每一行： 让 当前答案前k小的数 都加上 这一行最小的数，然后加入堆中 因为加的这个数是最小的，所以加上以后，它都有可能成为答案。 之后，将这一行其他的数加上 可以加的数 ，然后加入堆中。 这个可以加的数 是指的是，加上前k小的数并且结果不超过当前堆中最大的数(因为一旦超过，就不可能再成为答案了)。 code：

or(int i=2;i<=n;i++)    {
            for(int j=1;j<=m;j++)            scanf("%lld",&a[j]);        sort(a+1,a+1+m);        memset(dui,0,sizeof(dui));        len=0;        for(int j=1;j<=k;j++)            add(b[1]+a[j]);//b为当前的答案        for(int j=2;j<=k;j++)        {
                if(b[j]+a[1]>=dui[1]) break;            else                for(int l=1;l<=k;l++)                {
                        if(b[j]+a[l]

完整代码：

#include
   
    using namespace std;#define maxn 90005#define ll long long ll dui[maxn],len=0,n,m,k,ans[maxn];ll b[maxn],a[maxn];void down(int x){
        int l = x*2;    while(l<=len)    {
            if(l
    
     
       dui[x])         {
                swap(dui[l],dui[x]);            x=l;l=x*2;        }        else break;    }}void up(int x){
        while(x>1)    {
            if(dui[x]>dui[x/2])        {
                swap(dui[x],dui[x/2]);            x/=2;        }        else break;    }}void gettop(int val){
        dui[1]=val;    down(1);}void add(int val){
        dui[++len]=val;    up(len);}int main(){
        scanf("%lld%lld%lld",&n,&m,&k);    for(int i=1;i<=m;i++)        scanf("%lld",&b[i]);    sort(b+1,b+1+m);    for(int i=2;i<=n;i++)    {
            for(int j=1;j<=m;j++)            scanf("%lld",&a[j]);        sort(a+1,a+1+m);        memset(dui,0,sizeof(dui));        len=0;        for(int j=1;j<=k;j++)            add(b[1]+a[j]);        for(int j=2;j<=k;j++)        {
                if(b[j]+a[1]>=dui[1]) break;            else                for(int l=1;l<=k;l++)                {
                        if(b[j]+a[l]
     
    
   

如有错误，欢迎指正

转载地址：http://fyuci.baihongyu.com/