洛谷 P1392 取数

题面

在做这道题前，先要会他的弱化版（实际一模一样，只是愚蠢的洛谷评测级别差了一档(睿智如姬无夜))

----------------------------------弱化版---------------------

弱化版

实际只是把矩阵行数改成两行而已

sol：先排序，后考虑一个序列a[1]+b[1],a[2]+b[1],a[3]+b[1],······,a[n-1]+b[1],a[n]+b[1];

显然对于上一个序列而言 a[1]+b[1]<=a[1]+b[2], a[2]+b[1]<=a[2]+b[2], a[3]+b[1]<=a[4]+b[2]

虽然上面反应的只是以a分成的n个组中a[i]+(b[1]到b[2]到b[3]···到b[n])每组序列严格递增

但是利用小根堆就可以完成要求了每次弹出堆顶元素，在压入弹出元素组别的下一个数

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=;

int n,a[N],b[N],size=,to[N];

struct node{int key,id;}heap[N*];

inline void Up(int x)

{

    while(x>)

    {

        if(heap[x].key<heap[x/].key)

        {

            swap(heap[x],heap[x/]); x/=;

        }else break;

    }return;

}

inline void Down(int x)

{

    int y=x*;

    while(y<=size)

    {

        if(y<size&&heap[y].key>heap[y+].key)y++;

        if(heap[x].key>heap[y].key)

        {

            swap(heap[x],heap[y]); x=y; y=x*;

        }else break;

    }return;

}

inline void Insert(int v,int id){heap[++size]=(node){v,id};Up(size);}

inline node Top(){return heap[];}

inline void Pop(){swap(heap[],heap[size]);size--;Down();}

int main()

{

    int i; node tmp; scanf("%d",&n);

    for(i=;i<=n;i++)scanf("%d",&a[i]); for(i=;i<=n;i++)scanf("%d",&b[i]); sort(a+,a+n+); sort(b+,b+n+);

    for(i=;i<=n;i++){Insert(a[i]+b[],i);to[i]=;}

    for(i=;i<=n;i++)

    {

        tmp=Top(); Pop(); printf("%d ",tmp.key); Insert(a[tmp.id]+b[++to[tmp.id]],tmp.id);

    }printf("\n");

}

----------------------------------强化版---------------------

这就是对于第一行，和第二行合并，得到新的序列，在用新序列与下一个合并，就解决了

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=;

int n,m,k,a[][N],b[N],size=,to[N];

struct node{int key,id;}heap[N*];

inline void Up(int x)

{

    while(x)

    {

        if(heap[x].key<heap[x/].key)

        {

            swap(heap[x],heap[x/]); x/=;

        }else break;

    }return;

}

inline void Down(int x)

{

    int y=x*;

    while(y<=size)

    {

        if(y<size&&heap[y].key>heap[y+].key)y++;

        if(heap[x].key>heap[y].key)

        {

            swap(heap[x],heap[y]); x=y; y=x*;

        }else break;

    }return;

}

inline void Insert(int key,int id){heap[++size]=(node){key,id};Up(size);}

inline node Top(){return heap[];}

inline void Pop(){swap(heap[],heap[size]);size--;Down();}

int main()

{

    int i,j,t=; node tmp; scanf("%d%d%d",&n,&m,&k);

    for(i=;i<=m;i++)scanf("%d",&a[t][i]); sort(a[t]+,a[t]+m+);

    for(i=;i<=n;i++)

    {

        t^=; for(j=;j<=m;j++)scanf("%d",&b[j]); sort(b+,b+m+); size=;

        for(j=;j<=k;j++)

        {

            Insert(a[t^][j]+b[],j); to[j]=;

        }

        for(j=;j<=k;j++)

        {

            tmp=Top(); Pop(); a[t][j]=tmp.key; Insert(a[t^][tmp.id]+b[++to[tmp.id]],tmp.id);

        }

    }for(i=;i<=k;i++)printf("%d ",a[t][i]);

}

巴特西

洛谷 P1392 取数

最新文章

热门文章