刷题笔记合集🔗

考勤信息

问题描述

K小姐是一家公司的人力资源经理，他需要根据员工的出勤记录来决定是否发放考勤奖励。公司规定了以下出勤状态：

• absent：缺勤
• late：迟到
• leaveearly：早退
• present：正常出勤

员工获得考勤奖励需满足以下全部条件：

1. 缺勤次数不超过 次；
2. 没有连续的迟到或早退；
3. 任意连续 天内，缺勤、迟到和早退的次数总和不超过 次。

请你帮助K小姐编写一个程序，判断每位员工是否能获得考勤奖励。

输入格式

第一行包含一个正整数 ，表示员工的总数。

接下来 行，每行包含若干个空格分隔的字符串，表示一名员工的出勤记录。

输出格式

输出 行，每行为 true 或 false，表示对应的员工是否能获得考勤奖励。

样例输入1

2
present 
present present

样例输出1

true
true

样例输入2

2
present
present absent present present leaveearly present absent

样例输出2

true
false

样例解释

数据范围

• 
• 每个员工的出勤记录不超过 条。

题解

滑动窗口

这道题目的核心在于如何高效地判断员工的出勤记录是否满足获得奖励的条件。我们可以使用滑动窗口的方法来解决这个问题。

首先，需要遍历每个员工的出勤记录，同时维护一个长度为 7 的滑动窗口。在遍历的过程中，我们需要检查以下几点：

1. 统计总的缺勤次数，如果超过 1 次，直接判定为不符合条件。
2. 检查是否有连续的迟到或早退，如果有，也不符合条件。
3. 在滑动窗口内，统计缺勤、迟到和早退的总次数，如果超过 3 次，不符合条件。

使用滑动窗口的好处是我们可以在 O(n) 的时间复杂度内完成判断，其中 n 是员工的出勤记录长度。这种方法既高效又直观，能够很好地解决这个问题。

在实现时，我们可以使用一个变量来记录窗口内的正常出勤次数，这样就可以通过简单的减法来得到异常出勤的次数，避免了重复计算。

参考代码

• Python

def check_award(attendance):
    absent_days = 0  # 记录缺勤天数
    present_days = 0  # 记录正常出勤天数
    late_early = ("late", "leaveearly")  # 定义迟到和早退的状态
    prev_status = ""  # 记录前一天的状态

    for i, status in enumerate(attendance):
        # 滑动窗口长度最大为7，如果超过7天，需要减去最早的一天
        if i >= 7:
            if attendance[i - 7] == "present":
                present_days -= 1

        # 处理当前状态
        if status == "absent":
            absent_days += 1
            if absent_days > 1:  # 缺勤超过1次，不符合条件
                return "false"
        elif status in late_early and prev_status in late_early:  # 连续迟到或早退，不符合条件
            return "false"
        elif status == "present":
            present_days += 1

        prev_status = status

        # 检查任意连续7天内，缺勤/迟到/早退是否超过3次
        window_size = min(i + 1, 7)
        if window_size - present_days > 3:
            return "false"

    return "true"

# 读取输入
emp_count = int(input())
records = [input().split() for _ in range(emp_count)]

# 处理每个员工的记录并输出结果
for record in records:
    print(check_award(record))

• C

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

#define MAX_DAYS 1000
#define MAX_EMPLOYEES 100

// 检查员工是否获得奖励
bool check_award(char attendance[][20], int days) {
    int absent_days = 0;  // 缺勤天数
    int present_days = 0;  // 正常出勤天数
    char prev_status[20] = "";  // 前一天的状态

    for (int i = 0; i < days; i++) {
        // 滑动窗口长度最大为7，如果超过7天，需要减去最早的一天
        if (i >= 7 && strcmp(attendance[i - 7], "present") == 0) {
            present_days--;
        }

        // 处理当前状态
        if (strcmp(attendance[i], "absent") == 0) {
            absent_days++;
            if (absent_days > 1) return false;  // 缺勤超过1次，不符合条件
        } else if ((strcmp(attendance[i], "late") == 0 || strcmp(attendance[i], "leaveearly") == 0) &&
                   (strcmp(prev_status, "late") == 0 || strcmp(prev_status, "leaveearly") == 0)) {
            return false;  // 连续迟到或早退，不符合条件
        } else if (strcmp(attendance[i], "present") == 0) {
            present_days++;
        }

        strcpy(prev_status, attendance[i]);

        // 检查任意连续7天内，缺勤/迟到/早退是否超过3次
        int window_size = (i + 1 < 7) ? (i + 1) : 7;
        if (window_size - present_days > 3) return false;
    }

    return true;
}

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        char attendance[MAX_DAYS][20];
        int days = 0;
        
        // 读取一个员工的出勤记录
        while (sc