E卷-手机App防沉迷系统 100分)

手机App防沉迷系统

题目描述

智能手机方便了我们的生活，但也占用了我们不少时间。为了合理规划每天使用手机 App 的时间，让我们在正确的时间做正确的事，现在开发一个"手机 App 防沉迷系统"。

系统的基本原理如下：

1. 在一天的 小时内，可以为每个 App 注册允许使用的时段。
2. 一个时间段内只能使用一个 App。
3. 每个 App 有一个优先级，用 到 的整数表示，数值越大优先级越高。在注册使用时段时，如果高优先级 App 的时段与低优先级 App 的时段冲突，系统会自动注销低优先级的 App 在冲突时段的使用权限。如果优先级相同，则先注册的 App 保留使用权限，后注册的 App 无法在冲突时段使用。

请你编写一个程序，根据输入的 App 注册信息，以及给定的查询时间点，返回该时间点可以使用的 App 名称。如果该时间点没有可用的 App，则返回字符串 "NA"。

输入格式

第一行包含一个正整数 （），表示需要注册的 App 数量。

接下来 行，每行包含一个 App 的注册信息，由 App 名称、优先级、起始时间、结束时间组成，四项数据以空格分隔：

• App 名称为仅由大小写英文字母和数字组成的字符串，长度不超过 。
• 优先级为 到 的整数，数字越大优先级越高。
• 起始时间和结束时间的格式为 HH:MM，保证 ，。起始时间严格小于结束时间。注册的时段包含起始时间点，但不包含结束时间点。

最后一行包含一个查询时间点，格式与起始时间和结束时间相同。

输出格式

输出一个字符串，表示查询时间点可用的 App 名称，或者 "NA" 表示该时间点没有可用的 App。

样例输入

2
App1 1 09:00 10:00
App2 2 11:00 11:30
09:30

样例输出

App1

样例解释

App1 注册了 : 到 : 的时段，查询时间点 : 落在该时段内，因此可以使用 App1。

样例输入

2
App1 1 09:00 10:00
App2 2 09:10 09:30
09:20

样例输出

App2

样例解释

App1 和 App2 注册的时段有冲突，但 App2 的优先级更高，因此 App1 在冲突时段 : 到 : 内的注册无效，查询时间点 : 只能使用 App2。

样例输入

2
App1 1 09:00 10:00
App2 2 09:10 09:30
09:50

样例输出

NA

样例解释

查询时间点 : 不在任何已注册的 App 可用时段内，因此输出 "NA"。

数据范围

对于 的数据，。 对于 的数据，。 对于 的数据，。

题解

模拟

首先,我们定义一个 App 类来表示每个 App 的注册信息,包括 App 的名称、优先级、起始时间和结束时间。我们可以把时间转换成以分钟为单位的整数,这样比较时间大小会更方便。然后,我们按照输入的顺序依次处理每个 App 的注册信息。对于每个待注册的 App,我们需要判断它的使用时段是否和已经注册的 App 有冲突。如果有冲突,就比较两个 App 的优先级:

• 如果待注册的 App 优先级更高,那么我们就把冲突的 App 从已注册列表中删除,然后把当前的 App 加入到已注册列表中。
• 如果待注册的 App 优先级不高于冲突的 App,那么当前的 App 就不能注册了。

我们可以用一个列表来维护已经注册的 App,每次注册新的 App 时,就遍历这个列表,检查是否有冲突。如果要删除冲突的 App,可以先记录下它们的位置,然后再一次性删除,避免在遍历列表的同时修改列表导致的问题。处理完所有的注册信息后,我们再来处理查询时间点。我们遍历已注册的 App 列表,找到包含查询时间点的 App,输出它的名称即可。如果没有找到,就输出 "NA"。

参考代码

• Python

class App:
    def __init__(self, name, priority, start_time, end_time):
        self.name = name
        self.priority = priority
        self.start_time = self.convert_time(start_time)  # 将时间字符串转换为分钟数
        self.end_time = self.convert_time(end_time)
    
    @staticmethod
    def convert_time(time_str):
        """将时间字符串转换为分钟数"""
        hours, minutes = map(int, time_str.split(':'))
        return hours * 60 + minutes

def main():
    n = int(input())  # 读入 App 数量
    apps = []
    for _ in range(n):
        name, priority, start_time, end_time = input().split()
        apps.append(App(name, int(priority), start_time, end_time))
    
    query_time_str = input()  # 读入查询时间点
    query_time = App.convert_time(query_time_str)
    
    registered_apps = []  # 已注册的 App 列表
    for app in apps:
        if app.start_time >= app.end_time:  # 起始时间大于等于结束时间,不能注册
            continue
        
        conflicting_apps = []  # 记录与当前 App 冲突的已注册 App
        can_register = True
        for registered_app in registered_apps:
            if not (registered_app.start_time >= app.end_time or app.start_time >= registered_app.end_time):
                # 如果时段冲突,比较优先级
                if app.priority > registered_app.priority:
                    conflicting_apps.append(registered_app)
                else:
                    can_register = False
                    break
        
        if can_register:
            registered_apps = [a for a in registered_apps if a not in conflicting_apps]  # 移除冲突的已注册 App
            registered_apps.append(app)  # 将当前 App 加入已注册列表
    
    # 在已注册的 App 中查找包含查询时间点的 App
    result = next((app.name for app in registered_apps if app.start_time <= query_time < app.end_time), "NA")
    print(result)  # 输出查询结果

if __name__ == '__main__':
    main()

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_N 100
#define MAX_NAME_LEN 20

typedef struct {
    char name[MAX_NAME_LEN + 1];
    int priority;
    int start_time;
    int end_time;
} App;

int convert_time(const char *time_str) {
    int hours, minutes;
    sscanf(time_str, "%d:%d", &hours, &minutes);
    return hours * 60 + minutes;
}

int main() {
    int n;
    scanf("%d", &n);  // 读入 App 数量
    
    App apps[MAX_N];
    for (int i = 0; i < n; i++) {
        char start_time_str[6], end_time_str[6];
        scanf("%s %d %s %s", apps[i].name, &apps[i].priority, start_time_str, end_time_str);
        apps[i].start_time = convert_time(start_time_str);
        apps[i].end_time = convert_time(end_time_str);
    }
    
    char query_time_str[6];
    scanf("%s", query_time_str);  // 读入查询时间点
    int query_time = convert_time(query_time_str);
    
    App *registered_apps[MAX_N];
    int num_registered_apps = 0;
    
    for (int i = 0; i < n; i++) {
        App *app = &apps[i];
        if (app->start_time >= app->end_time) {  // 起始时间大于等于结束时间,不能注册
            continue;
        }
        
        int conflicting_apps[MAX_N];
        int num_conflicting_apps = 0;
        bool can_register = true;
        
        for (int j = 0; j < num_registered_apps; j++) {
            App *registered_app = registered_apps[j];
            if (!(registered_app->start_time >= app->end_time || app->start_time >= registered_app->end_time)) {
                // 如果时段冲突,比较优先级
                if (app->priority > registered_app->priority) {
                    conflicting_apps[num_conflicting_apps++] = j;
                } else {
                    can_register = false;
                    break;
                }
            }
        }
        
        if (can_register) {
            // 移除冲突的已注册 App
            for (int j = num_conflicting_apps - 1; j >= 0; j--) {
                int idx = conflicting_apps[j];
                for (int k = idx; k < num_registered_apps - 1; k++) {
                    registered_apps[k] = registered_apps[k + 1];
                }
                num_registered_apps--;
            }
            registered_apps[num_registered_apps++] = app;  // 将当前 App 加入已注册列表
        }
    }
    
    // 在已注册的 App 中查找包含查询时间点的 App
    const char *result = "NA";
    for (int i = 0; i < num_registered_apps; i++) {
        App *app = registered_apps[i];
        if (app->start_time <= query_time && query_time < app->end_time) {
            result = app->name;
            break;
        }
    }
    
    printf("%s\n", result);  // 输出查询结果
    
    return 0;
}

• Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class App {
    String name;
    int priority;
    int startTime;
    int endTime;

    App(String name, int priority, String startTime, String endTime) {
        this.name = name;
        this.priority = priority;
        this.startTime = convertTime(startTime);
        this.endTime = convertTime(endTime);
    }

    private static int convertTime(String timeStr) {
        String[] parts = timeStr.split(":");
        int hours = Integer.parseInt(parts[0]);
        int minutes = Integer.parseInt(parts[1]);
        return hours * 60 + minutes;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 读入 App 数量
        scanner.nextLine();  // 消耗换行符

        List<App> apps = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String[] info = scanner.nextLine().split(" ");
            String name = info[0];
            int priority = Integer.parseInt(info[1]);
            String startTime = info[2];
            String endTime = info[3];
            apps.add(new App(name, priority, startTime, endTime));
        }

        String queryTimeStr = scanner.nextLine();  // 读入查询时间点
        int queryTime = App.convertTime(queryTimeStr);

        List<App> registeredApps = new ArrayList<>();  // 已注册的 App 列表
        for (App app : apps) {
            if (app.startTime >= app.endTime) {  // 起始时间大于等于结束时间,不能注册
                continue;
            }

            List<App> conflictingApps = new ArrayList<>();  // 记录与当前 App 冲突的已注册 App
            boolean canRegister = true;
            for (App registeredApp : registeredApps) {
                if (!(registeredApp.startTime >= app.endTime || app.startTime >= registeredApp.endTime)) {
                    // 如果时段冲突,比较优先级
                    if (app.priority > registeredApp.priority) {
                        conflictingApps.add(registeredApp);
                    } else {
                        canRegister = false;
                        break;
                    }
                }
            }

            if (canRegister) {
                registeredApps.removeAll(conflictingApps);  // 移除冲突的已注册 App
                registeredApps.add(app);  // 将当前 App 加入已注册列表
            }
        }

        // 在已注册的 App 中查找包含查询时间点的 App
        String result = registeredApps.stream()
                .filter(app -> app.startTime <= queryTime && queryTime < app.endTime)
                .map(app -> app.name)
                .findFirst()
                .orElse("NA");

        System.out.println(result);  // 输出查询结果
    }
}

#include <bits/stdc++.h>

using namespace std;

class App {
public:
    string name;
    int priority;
    int startTime;
    int endTime;

    App(string name, int priority, string startTime, string endTime)
        : name(name), priority(priority), startTime(convertTime(startTime)), endTime(convertTime(endTime)) {}

public:
    static int convertTime(const string& timeStr) {
        int hours, minutes;
        char colon;
        stringstream ss(timeStr);
        ss >> hours >> colon >> minutes;
        return hours * 60 + minutes;
    }
};

int main() {
    int n;
    cin >> n;  // 读入 App 数量
    cin.ignore();  // 消耗换行符

    vector<App> apps;
    for (int i = 0; i < n; i++) {
        string name, startTime, endTime;
        int priority;
        cin >> name >> priority >> startTime >> endTime;
        apps.emplace_back(name, priority, startTime, endTime);
    }

    string queryTimeStr;
    cin >> queryTimeStr;  // 读入查询时间点
    int queryTime = App::convertTime(queryTimeStr);

    vector<App*> registeredApps;  // 已注册的 App 列表
    for (auto& app : apps) {
        if (app.startTime >= app.endTime) {  // 起始时间大于等于结束时间,不能注册
            continue;
        }

        vector<App*> conflictingApps;  // 记录与当前 App 冲突的已注册 App
        bool canRegister = true;
        for (auto registeredApp : registeredApps) {
            if (!(registeredApp->startTime >= app.endTime || app.startTime >= registeredApp->endTime)) {
                // 如果时段冲突,比较优先级
                if (app.priority > registeredApp->priority) {
                    conflictingApps.push_back(registeredApp);
                } else {
                    canRegister = false;
                    break;
                }
            }
        }

        if (canRegister) {
            // 移除冲突的已注册 App
            registeredApps.erase(remove_if(registeredApps.begin(), registeredApps.end(),
                [&conflictingApps](App* a) {
                    return find(conflictingApps.begin(), conflictingApps.end(), a) != conflictingApps.end();
                }), registeredApps.end());
            registeredApps.push_back(&app);  // 将当前 App 加入已注册列表
        }
    }

    // 在已注册的 App 中查找包含查询时间点的 App
    auto it = find_if(registeredApps.begin(), registeredApps.end(),
        [queryTime](App* app) { return app->startTime <= queryTime && queryTime < app->endTime; });
    string result = (it != registeredApps.end()) ? (*it)->name : "NA";

    cout << result << endl;  // 输出查询结果

    return 0;
}