ACM_Someone like you

Root :: AOAPC I: Beginning Algorithm Contests -- Training Guide (Rujia Liu) :: Chapter 3. Data Structures :: Fundamental Data Structures :: Examples

//UVA 11997 - K Smallest Sums
/*
題意：一個k*k數組，每行取一個元素 求和，共有k^k種可能，找到k種最小的和
輸出。
第一次是O(n*n)超時了，改用歸并排序，優先隊列實現，時間降低為nlogn
思路：初始化：每行sort排序；然后每兩行合并 優先隊列存貯前K小數，繼續合并完。
輸出前k個元素即可。
*///AC
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int M=800;
int a[M][M];
int k;
struct Node
{
    int sum;//a1[i][j]+a2[i+1][j]
    int ct;//標記是否到了最后一行和k 比大小
    Node(int x , int y):sum(x), ct(y){}
    bool operator <(const Node &e)const//重載<
    {
        return sum>e.sum;//升序排列元素
    }
};
int merge(int *A,int *B)
{
    int i,j;
    priority_queue <Node> s;
    for(i=0;i<k;i++)
    s.push(Node(A[i]+B[0],0));//元素入隊列
    for(i=0;i<k;i++)
    {
        Node node =s.top();//找到隊列中最小元素賦值；
        s.pop();
         A[i]=node.sum;
        int ct=node.ct;
        if(ct+1<k)//沒有掃描到最后一行
        s.push(Node(node.sum-B[ct]+B[ct+1],ct+1));//都merge歸并為一行記為A
    }
}
int main()
{
    int i,j;
    while(scanf("%d",&k)!=EOF)
    {
        for(i=0;i<k;i++)
        {
            for(j=0;j<k;j++)
            scanf("%d",&a[i][j]);//  sort(a[i],a[i]+k);//
          sort(&a[i][0],&a[i][0]+k);
        }
        for(i=1;i<k;i++)
        merge(a[0],a[i]);//每兩行歸并排序。
        for(i=0;i<k-1;i++)
        printf("%d ",a[0][i]);
        printf("%d",a[0][k-1]);//最后一個數必須獨立輸出
        printf("\n");
    }
    return 0;
}
//O(n*n)
/*//
//超時
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int M=800;
int n;
int a[M][M],b[M*M];
void f()
{
    memset(b,0,sizeof(b));
    int i,j,k;
    int ct=0,sum=0;
    for(i=0;i<n;i++)
        ct+=a[i][0];
    for(i=0;i<n;i++)
    {
        for(j=1;j<n;j++)
        {
            b[sum++]=a[i][j]-a[i][j-1];
        }
    }sort(b,b+sum);
    printf("%d ",ct);
    for(i=0;i<n-1;i++)
    printf("%d ",ct+b[i]);
    printf("\n");
}
int main()
{
    int i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                scanf("%d",&a[i][j]);//&b[j]);
            }
            sort(&a[i][0],&a[i][0]+n);//每行升序排序
            //sort(b,b+n);
          // printf("##########\n"); //memcpy(&a[i][0],b,sizeof(a));//把a數組全部數字給b，a自己保留。

        }f();
    }
    return 0;
}


*/