POJ 2442 Sequence

Sequence
Time Limit: 6000MS

Memory Limit: 65536K
Total Submissions: 6120

Accepted: 1897
Description
Given m sequences, each contains n non-negative integer. Now we may select one number from each sequence to form a sequence with m integers. It's clear that we may get n ^ m this kind of sequences. Then we can calculate the sum of numbers in each sequence, and get n ^ m values. What we need is the smallest n sums. Could you help us?
Input
The first line is an integer T, which shows the number of test cases, and then T test cases follow. The first line of each case contains two integers m, n (0 < m <= 100, 0 < n <= 2000). The following m lines indicate the m sequence respectively. No integer in the sequence is greater than 10000.
Output
For each test case, print a line with the smallest n sums in increasing order, which is separated by a space.
Sample Input

Sample Output

3 3 4

Source
POJ Monthly ,Guang Lin

m개의 질서표의 앞 n개의 최소와 m-1개의 질서표의 qian의 최소와 m개의 질서표로 이루어질 수 있다.이런 식으로 미루어 보면 먼저 이 문제를 참고할 수 있다http://www.cnblogs.com/jackge/archive/2013/04/28/3049766.html

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

const int N=2010;

int m,n,a[N],b[N],c[N],d[N];

struct node{
    int id,x;
    bool operator < (const node &a) const{
        return a.x<x;
    }
};

void solve(){
    for(int i=0;i<n;i++)
        d[i]=0;
    //priority_queue<node,vector<node>,cmp> q;
    priority_queue<node> q;
    node cur;
    for(int i=0;i<n;i++){
        cur.id=i;
        cur.x=a[i]+b[d[i]];
        q.push(cur);
    }
    int k=n,cnt=0;
    while(k--){
        cur=q.top();
        q.pop();
        c[cnt++]=cur.x;
        cur.x=a[cur.id]+b[++d[cur.id]];
        q.push(cur);
    }
    for(int i=0;i<n;i++)
        a[i]=c[i];
}

int main(){

    //freopen("input.txt","r",stdin);

    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&m,&n);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        for(int i=1;i<m;i++){
            for(int j=0;j<n;j++)
                scanf("%d",&b[j]);
            sort(b,b+n);
            solve();
        }
        for(int i=0;i<n-1;i++)
            printf("%d ",a[i]);
        printf("%d
",a[n-1]);
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

POJ 2442 Sequence

Sequence Time Limit: 6000MS Memory Limit: 65536K Total Submissions: 6120 Accepted: 1897 Description Given m sequences, e...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

POJ 2442 Sequence

좋은 웹페이지 즐겨찾기