2475: Matrix Tops-CSDN博客

本文链接：https://blog.csdn.net/kongming_acm/article/details/5726050

本文介绍了一个有趣的编程问题：如何找出矩阵中前Z个最小值。矩阵由两个数组通过特定方式生成，文章提供了输入输出示例及算法实现思路。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

2475: Matrix Tops

Result	TIME Limit	MEMORY Limit	Run Times	AC Times	JUDGE
	5s	131072K	679	78	Standard

This is an interesting problem about finding the first Z minimum numbers of a Matrix. The matrix is defined as below:

The matrix C has N rows and M columns.
C[i][j](0<=i<N,0<=j<M) is the number at the i-th row and j-th column of the Matrix.
Two arrays A and B is used to represent C. A is an array of N numbers and B is an array of M numbers. C[i][j]=A[i]*B[j] all indices start from 0.
1<=N<=10000，1<=M<=10000，0<=Z<=N*M and Z<=2000. Integer is enough for this problem, the multiplication won't overflow.

Given the two arrays A and B, your task is to find the first Z minimum numbers of the Matrix C. The Z numbers should be in increasing order.

Input

There will be several cases. Each case includes three lines.
Line 1: Three integers N, M and Z
Line 2: N integers of array A
Line 3: M integers of array B
The input terminates when N=M=Z=0

Output

For each test case, output the first Z minimum numbers in Matrix C in increasing order. A single number takes up a line.

Sample Input

Sample Output

Problem Source: sharang

This problem is used for contest: 101

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n,m,z;
    int a[10002],b[10002],l[10002],num[10002];
    int flag[10002];
    while(scanf("%d%d%d",&n,&m,&z)==3)
    {
        if(n==0&&m==0&&z==0) break;
        memset(flag,0,sizeof(flag));
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        for(int i=0;i<m;i++) scanf("%d",&b[i]);
        sort(a,a+n);
        sort(b,b+m);
        for(int i=0;i<m;i++) if(b[i]<0) flag[i]=1;
        for(int i=0;i<m;i++) if(flag[i]) l[i]=n-1;else l[i]=0;
        for(int i=0;i<m;i++)
        {
            if(b[i]>=0) num[i]=a[0]*b[i];
            else num[i]=a[n-1]*b[i];
        }
        while(z--)
        {
           int minc=(1<<31)-1,p=0;
         // for(int i=0;i<m;i++) cout<<i<<"..."<<flag[i]<<"..."<<l[i]<<"..."<<num[i]<<endl;
           for(int i=0;i<m;i++)
           {
               if(flag[i]==2) continue;
               if(num[i]<minc) minc=num[i],p=i;
           }
           printf("%d/n",minc,p);
           //cout<<"....."<<flag[p]<<"....."<<l[p]<<endl;
           if(flag[p]==1)
           {
               l[p]--;
            //   cout<<"******"<<flag[p]<<"....."<<l[p]<<endl;
               if(l[p]<0) flag[p]=2;
               else num[p]=a[l[p]]*b[p];
             // cout<<"******"<<flag[p]<<"....."<<l[p]<<endl;
           }
           else
           {
               l[p]++;
               if(l[p]==n) flag[p]=2;
               else num[p]=a[l[p]]*b[p];
           }
          // cout<<"....."<<flag[p]<<"....."<<l[p]<<endl;
          // cout<<"..........................."<<endl;
        }
    }
    return 0;
}