[编程|500分] 开关灯

时间限制:C/C++ 1秒,其他语言 2秒
空间限制:C/C++ 262144K,其他语言 524288K
64bit IO Format: %lld

题目描述

美团的办公室一共有n层,每层有m个会议室,可以看成是一个n*m的网格图。工程师们每天的工作需要协作的地方很多,经常要到会议室开会解决各种问题。公司是提倡勤俭节约的,因此每次会议室只在使用时才开灯。
当一个工程师进入会议室时,假设没有其他人,他会把灯打开。
当一个工程师离开会议室时,假设没有其他人,他会把灯关掉。
现在给出一系列工程师进出会议室的记录,请问在此过程中,最多有多少会议室的灯是亮着的?请输出亮灯数最多时,每个会议室的明暗状态。

输入描述:

第一行三个整数n,m,k,分别表示总行数、总列数、工程师的进出记录数。 接下来k行,每行三个整数和一个字符串x, y, z, t,表示t时间点有一条记录,z=0表示x行y列的会议室有个工程师进入会议室了,z=1表示x行y列的房间有个工程师离开会议室了。
假设一开始所有会议室里都是没人的。 1 <= n, m <= 500 1 <= k <= 100,000
t是HH:MM:SS.SSS的形式,其中HH表示小时,MM表示分钟,SS.SSS表示秒数。(因为工程师有非常强大的时间观念,所以对于他们来说,时间是精确到0.001秒的)
数据保证t在18:00:00.000到23:59:59.999之间,且没有两条记录的时间是完全一样的。数据不保证记录以t升序的形式给出。
1 <= x <= n
1 <= y <= m
z∈{0, 1}
数据保证没有从空会议室离开的情况。
数据保证所有的时间格式合法。HH,MM均为长度为2的字符串,SS.SSS为长度为6的字符串。

输出描述:

输出n行每行m个整数,第i行第j列表示在亮灯数最多的时刻,第i行第j列的会议室的亮灯情况,1表示亮着,0表示没亮。
如果存在多次亮灯数最多的时刻,输出最后一次时的情况。

示例1

输入

2 2 4
1 1 0 18:00:00.000
1 1 1 20:00:00.000
1 1 0 18:00:01.000
1 2 0 18:00:02.000

输出

11
00

题解

简单题。首先按照时间顺序排序,然后依次模拟进出即可。

代码

#include<iostream>
#include<bitset>
#include<string>
#include<string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <math.h>
#include <stdio.h>
#include <set>
#include <queue>
#include <stack>
using namespace std;
struct jt
{
    int time, n, m, t;
};
bool pd(jt a, jt b) {
    return a.time < b.time;
}
int n, m, k, q1, q2, q3;
int fj[505][505];
int h, mi, s, ms, maxnow;
bitset<300100> now;
bitset<300100> ans;
vector<jt> input;
int num;
int main() {
    cin >> n >> m >> k;
    while (k--) {
        scanf("%d %d %d %d:%d:%d.%d", &q1, &q2, &q3, &h, &mi, &s, &ms);
        input.push_back({ h * 10000000 + mi * 100000 + s * 1000 + ms,q1,q2,q3 });
    }
    sort(input.begin(), input.end(), pd);
    for (auto i : input) {
        if (i.t) {
            fj[i.n][i.m]--;
            if (!fj[i.n][i.m]) {
                num--;
                now.reset(i.n*m + i.m);
            }
        }
        else {
            if (!fj[i.n][i.m]) {
                num++;
                now.set(i.n*m + i.m);
            }
            fj[i.n][i.m]++;
        }
        if (num >= maxnow) {
            ans = now;
            maxnow = num;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (ans[i*m + j])printf("1");
            else printf("0");
        }
        cout << endl;
    }
}

标签: none

添加新评论