【202312-1】仓库规划

题在最下面

算法1(没有2, 这只是一个模板)

(暴力剪枝?) $O(n^2/2*m-n/2*m)$

虽然但是，可能网上文章看多了，或者csp有大小次，反正没想到直接暴力也能满分AC
(2024.10.31考古，csp旧版模拟官网前3道都能暴力AC，是我草率了)
暴力已经有很多题解了，双重循环（循环展开）也有俩
$(平均O(n)从10^7堪堪剪到10^6, 即便优化成双重循环, 也就是10^5)$
(碰上极端数据甚至不如暴力枚举, 单纯图一乐)
虽然实际上也没剪到什么，但还是写一写吧

时间复杂度

C++ 代码

#include <iostream>

using namespace std;
typedef long long ll;

int compare(ll *r, int &M, int &i, int &j){
    int flag=0;
    for(int k=0;k<M;k++){
        if(r[i*M+k]<r[j*M+k]){
            flag++;
        }else if(r[i*M+k]>r[j*M+k]){
            flag--;
        }
    }
    return flag/M;
}

void findSuper(ll *r, int *ans, int &M, int &N){
    for(int i=0;i<N;i++){
        int j=i+1;
        while(j<N){
            if(ans[j]!=0){
                j++;
                continue;
            }
            int mark=compare(r, M, i, j);
            // i的下级仓库是j, 也就是j的上级仓库是i
            if(mark==-1&&ans[j]==0){
                ans[j]=i+1;
            }else if(mark==1&&ans[i]==0){
                ans[i]=j+1;
            }
            j++;
        }
        printf("%d\n",ans[i]);
    }
}

int main(){
    int N,M;
    cin>>N>>M;
    ll *repo=new ll[M*N];

    for(int i=0;i<M*N;i++){
        scanf("%lld", &repo[i]);
    }
    int *ans=new int[N]{0};
    findSuper(repo, ans, M, N);

    return 0;
}

$ $

$ $

题目背景

西西艾弗岛上有很多仓库，现在需要找到这些仓库的上下级关系

题目描述

西西艾弗岛上共有 $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$ 。

输入输出样例

样例输入 #1

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

样例输出 #1

3
1
0
3

提示

数据范围

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