【问题描述】有一部手机记录了一些来电信息。每条信息包含日期月和日、时间小时和分钟以及号码。能记录的来电数量是有限的。你发现这个限制数量很快就要达到了因此准备删除一些来电记录。在选择删除记录的时候你需要考虑下面两个限制： 1 有一些重要的来电记录你要保留。 2 你想让留下来的这些记录能够恢复来电的年份注意这是手机没有记录的。恢复的方法在下面描述。计算出在满足上述限制的条件下最少需要保留的

【算法描述】

1. 将输入的来电记录按照时间戳从早到晚排序。
2. 统计所有需要保留的来电记录数量，初始值为0。
3. 遍历排序后的来电记录列表：
   • 如果当前记录是需要保留的记录，则将保留记录数量加1。
   • 如果当前记录是不需要保留的记录，则判断是否与前一条记录是同一年的，如果是则将保留记录数量加1。
4. 输出保留记录数量。

【伪代码】 minSavedRecords(records): sort(records) # 将记录按照时间戳排序 savedRecords = 0 # 保留记录数量 for i = 0 to length(records) - 1: if records[i].type == '+': savedRecords += 1 else if records[i].type == '-': if i > 0 and isSameYear(records[i], records[i-1]): savedRecords += 1 return savedRecords

isSameYear(record1, record2): if record1.month > record2.month: return True else if record1.month < record2.month: return False else: if record1.day > record2.day: return True else if record1.day < record2.day: return False else: if record1.hour > record2.hour: return True else if record1.hour < record2.hour: return False else: if record1.minute >= record2.minute: return True else: return False

【复杂性分析】 时间复杂性：排序的时间复杂性为O(nlogn)，遍历记录的时间复杂性为O(n)，所以总的时间复杂性为O(nlogn)。 空间复杂性：只需要常量级的额外空间，所以空间复杂性为O(1)。

【C语言代码】 #include <stdio.h>

typedef struct { int month; int day; int hour; int minute; char type; } Record;

int isSameYear(Record record1, Record record2) { if (record1.month > record2.month) { return 1; } else if (record1.month < record2.month) { return 0; } else { if (record1.day > record2.day) { return 1; } else if (record1.day < record2.day) { return 0; } else { if (record1.hour > record2.hour) { return 1; } else if (record1.hour < record2.hour) { return 0; } else { if (record1.minute >= record2.minute) { return 1; } else { return 0; } } } } }

int minSavedRecords(Record records[], int n) { // 排序 for (int i = 0; i < n-1; i++) { for (int j = 0; j < n-i-1; j++) { if (isSameYear(records[j], records[j+1])) { // 交换位置 Record temp = records[j]; records[j] = records[j+1]; records[j+1] = temp; } } }

int savedRecords = 0;
for (int i = 0; i < n; i++) {
    if (records[i].type == '+') {
        savedRecords++;
    } else if (records[i].type == '-') {
        if (i > 0 && isSameYear(records[i], records[i-1])) {
            savedRecords++;
        }
    }
}

return savedRecords;

}

int main() { int n; scanf("%d", &n); Record records[n]; for (int i = 0; i < n; i++) { scanf("%d:%d:%d:%d %*s %c", &records[i].month, &records[i].day, &records[i].hour, &records[i].minute, &records[i].type); } int minSaved = minSavedRecords(records, n); printf("%d\n", minSaved); return 0;