E卷-手机App防沉迷系统 100分)
手机App防沉迷系统
题目描述
智能手机方便了我们的生活,但也占用了我们不少时间。为了合理规划每天使用手机 App 的时间,让我们在正确的时间做正确的事,现在开发一个"手机 App 防沉迷系统"。
系统的基本原理如下:
- 在一天的 小时内,可以为每个 App 注册允许使用的时段。
- 一个时间段内只能使用一个 App。
- 每个 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;
}
#OD#本专栏收集并整理了一些刷题笔记