hihocoder 1856 构造矩阵

构造矩阵

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

对于一个N × M的整数矩阵A，小Hi知道每一行的整数之和依次是P1, P2, ... PN，每一列的整数整数之和依次是Q1, Q2, ... QM。  

你能构造出一个矩阵A，满足每个元素Aij都是非负的，并且满足上述行列之和吗？

输入

第一行包含两个整数N和M。  

第二行包含N个整数，P1, P2, ... PN。  

第三行包含M个整数，Q1, Q2, ... QM。  

输入保证有解。  

1 ≤ N, M ≤ 100  

1 ≤ Pi, Qi ≤ 100000

输出

输入一个N × M的矩阵，满足题目中的要求。如果有多解，你可以输出任意一个。

样例输入

3 3  
15 15 15  
15 15 15

样例输出

8 1 6  
3 5 7  
4 9 2

乱搞就可以，DFS，咋都能做，

看下面的C++  代码

每次都对这个位置所在的行和列进行填充，随便填就可以

#include <iostream>
#include<math.h>
#include<vector>
#include<string.h>
using namespace std;
int a[105][105];
int x[105];
int y[105];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    memset(a,0,sizeof(a));
    for(int i=0; i<n; i++)
        scanf("%d",&x[i]);
    for(int j=0; j<m; j++)
        scanf("%d",&y[j]);
    int i=0,j=0;

    while(1)
    {
        if(x[i]>y[j])
        {
            a[i][j]=y[j];
            x[i]=x[i]-y[j];
            j++;

        }
        else if(x[i]<y[j])
        {
            a[i][j]=x[i];
            y[j]=y[j]-x[i];
            i++;
        }
        else
        {
            a[i][j]=x[i];
            i++;
            j++;
        }
        if(i>=n||j>=m)
            break;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            printf("%d",a[i][j]);
            if(j!=m-1)
                printf(" ");
            else
                printf("\n");
        }
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int[][] matrix = new int[N][M];

        for (int i = 0; i < N; i++) {
            matrix[i][0] = in.nextInt();
        }
        int[] Ms = new int[M];
        for (int i = 0; i < M; i++) {
            Ms[i] = in.nextInt();
        }

        for (int i = 1; i < M; i++) {
            int temp = Ms[i];
            for (int j = 0; j < N; j++) {
                if (temp > matrix[j][0]) {
                    temp -= matrix[j][0];
                    matrix[j][i] = matrix[j][0];
                    matrix[j][0] = 0;
                } else if (temp <= matrix[j][0]) {
                    matrix[j][0] -= temp;
                    matrix[j][i] = temp;
                    temp = 0;
                }
                if (temp == 0) break;
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                System.out.print(matrix[i][j]+" ");
            }
            System.out.println();
        }
    }
}