AcWing:5415. 仓库规划

描述

西西艾弗岛上共有?n?个仓库，依次编号为?1～n。

每个仓库均有一个?m?维向量的位置编码，用来表示仓库间的物流运转关系。

具体来说，每个仓库?i?均可能有一个上级仓库?j，满足：仓库?j?位置编码的每一维均大于仓库?i?位置编码的对应元素。

比如编码为?(1,1,1) 的仓库可以成为?(0,0,0) 的上级，但不能成为?(0,1,0) 的上级。

如果有多个仓库均满足该要求，则选取其中编号最小的仓库作为仓库?i?的上级仓库；如果没有仓库满足条件，则说明仓库?i?是一个物流中心，没有上级仓库。

现给定?n?个仓库的位置编码，试计算每个仓库的上级仓库编号。

输入格式

输入共?n+1 行。

输入的第一行包含两个正整数?n?和?m，分别表示仓库个数和位置编码的维数。

接下来?n?行依次输入?n?个仓库的位置编码。其中第?i?行（1≤i≤n）包含?m?个整数，表示仓库?i 的位置编码。

输出格式

输出共?n?行。

第?i?行（1≤i≤n）输出一个整数，表示仓库?i?的上级仓库编号；如果仓库?i?没有上级，则第?i?行输出?0。

数据范围

50%50%?的测试数据满足?m=2；
全部的测试数据满足?0<m≤10、0<n≤1000，且位置编码中的所有元素均为绝对值不大于?10^6 的整数。

输入样例：

4 2
0 0
-1 -1
1 2
0 -1

输出样例：

3
1
0
3

样例解释

对于仓库?2：(?1,?1) 来说，仓库?1：(0,0) 和仓库?3：(1,2) 均满足上级仓库的编码要求，因此选择编号较小的仓库?1?作为其上级。

没什么好说的水题,上代码

/* 水题,没什么算法 */

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010 , M = 20; // 限制范围

/* 定义 */
int n , m;
int a[N][M];

/* 比较函数 */
int cmp(int x)
{
    int ans = 0; // 初始化赋值0
    for (int i = 1; i <= n; i ++ )
    {
        bool f = true;
        if(i == x) continue; // 不与自身比较
        for (int j = 0; j < m; j ++ )
        {
            if(a[x][j] >= a[i][j])
            {
                f = false;
                break;
            }
        }
        if(f)
        {
            ans = i;
            break;
        }
    }
    return ans;
}

int main()
{
    /* 读入 */
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> a[i][j];

    /* 直接调用输出 */
    for (int i = 1; i <= n; i ++ )
    {
        cout << cmp(i) << endl; 
    }
    
    return 0;
}