题解：CF411B Multi-core Processor

OIerJiang_1017 · 2024-12-16 13:34:09 · 题解

CF411B 题目传送门

题目大意

有编号从 1 到 n 的 n 个处理器和编号从 1 到 k 的 k 个存储单元，一共有 1 到 m 的 m 个时间段，第 i 个处理器会在第 j 个时间段给存储单元 x_{ij} 发送信号，如果 x_{ij}=0 表示处理器 i 在第 j 号时间段没有发送信号。如果有多个处理器在同一时间段给同一存储单元发送信号，则这些处理器和这个存储单元都将会被锁定。被锁定的处理器不能再发送信号，被锁定的单元不能再接收信号。如果未被锁定的处理器向锁定的存储单元发送信号，则该处理器也会被锁定。给定每个处理器在各个时间段发送信号的目标存储单元编号，请你计算出每个处理器被锁定的时间段。如果不会被锁定则返回 0。

解决思路

注意数据范围：1 \leq n,m,k \leq 100，可以直接想到大模拟。

代码展示

#include<bits/stdc++.h>
using namespace std;

const int N = 110;
int n, m, k, a[N][N];
int cnt[N], ans[N];
bool vis[N];

int main()
{   //建议scanf,更快
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]); 
    for(int i = 1; i <= m; i++)
    {
        memset(cnt, 0, sizeof(cnt));
        for(int j = 1; j <= n; j++)
        {
            if(ans[j] || !a[j][i] == 0)//处理器被锁定
                continue;             //或没有发出指令
            if(vis[a[j][i]])
            {
                ans[j] = i;
                continue;
            }//处理器向已锁定的单元发送指令
            cnt[a[j][i]]++;//统计每个单元接收到的指令数
        }
        for(int j = 1; j <= n; j++)
        {
            if(ans[j]) continue;//处理器已锁定，跳过
            if(cnt[a[j][i]] >= 2)
            //有多个处理器同时向某个单元发送指令
            {
                ans[j] = i;
                vis[a[j][i]] = 1;
                //单元和处理器均被锁定
            }
        }       
    }
    for(int i = 1; i <= n; i++)//建议printf,更快
        printf("%d\n", ans[i]);
    return 0;
}