CCF CSP 201712-3.Crontab

发表于 | 更新于 | 分类于 | 浏览 次
字数统计: 2.2k

样例输入

1
2
3
4
3 201711170032 201711222352
0 7 * * 1,3-5 get_up
30 23 * * Sat,Sun go_to_bed
15 12,18 * * * have_dinner

样例输出

201711170700 get_up
201711171215 have_dinner
201711171815 have_dinner
201711181215 have_dinner
201711181815 have_dinner
201711182330 go_to_bed
201711191215 have_dinner
201711191815 have_dinner
201711192330 go_to_bed
201711200700 get_up
201711201215 have_dinner
201711201815 have_dinner
201711211215 have_dinner
201711211815 have_dinner
201711220700 get_up
201711221215 have_dinner
201711221815 have_dinner


分析：

解析输入的配置信息，将符号（星号、减号以及逗号）和英文缩写转换为对应的数字。

求解算法如下：

1
2
3
4
5
6
7
8
9
10
11
遍历从开始时间y1年到结束时间y2年中的所有年份y：
	遍历所有符合配置信息的月份m:
		遍历所有符合配置信息的日期d（m月的第d天）:
			若d超过了y年m月的最大天数:
				continue
			若y年m月d日的星期在day of week中:
				遍历所有符合配置信息的小时h:
					遍历所有符合配置信息的分钟min:
						计算任务调度的时间date
						若 s <= date < t:
							以date为键，执行的命令cmd为值，存入哈希表中

1.1970年1月1日是星期四。

2.星号只能单独出现，减号和逗号可以配合出现。

3.英文缩写不区分大小写。英文缩写和数值可以混合使用。

4.包含系统运行的开始时间s，但不包含结束时间t，即[s,t)。

5.按照时间先后顺序输出。如果同一时刻有多条命令满足调度条件，则按照输入给出的顺序输出。

因此，哈希表必须是有序的。在C++中，可以使用map；Java中，可以使用TreeMap。

6.<minutes>、<hours>、<day of month>、<month>和<day of week>中的值可能会重复出现，注意去重。

  • C++版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <sstream>
#include <regex>
using namespace std;

const long long HUNDRED_MILLION = 100000000, MILLION = 1000000;

int months[2][13] = { { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }, 
                     { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 } };

// 将字符串形式的月份（星期）映射为数字形式
map<string, int> monthAndWeekMap = { { "jan", 1 }, { "feb", 2 }, { "mar", 3 }, {
		"apr", 4 }, { "may", 5 }, { "jun", 6 }, { "jul", 7 }, { "aug", 8 }, {
		"sep", 9 }, { "oct", 10 }, { "nov", 11 }, { "dec", 12 }, { "sun", 0 }, {
		"mon", 1 }, { "tue", 2 }, { "wed", 3 }, { "thu", 4 }, { "fri", 5 }, {
		"sat", 6 } };

// 存储输入的配置信息，0-minutes,1-hours,2-day of month,3-month,4-day of week
set<int> cfg[5];
map<long long, vector<string> > dict;

// 是否为闰年
bool isLeapYear(int year) {
	return year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);
}

// 判断字符串是否为数字
bool isDigit(string str) {
	for (int i = 0; i < str.size(); i++) {
		if (str[i] < '0' || str[i] > '9') {
			return false;
		}
	}
	return true;
}

// 将字符串转换为小写形式
string toLowerCase(string str) {
	for (int i = 0; i < str.size(); i++) {
		if ('A' <= str[i] && str[i] <= 'Z') {
			str[i] += 32;
		}
	}
	return str;
}

// 计算y年m月d日是星期几，已知1970年1月1日是星期四
int dayOfWeek(int y, int m, int d) {
	int days = 0;
	for (int i = 1970; i < y; i++) {
		days += 365;
		if (isLeapYear(i)) {
			days += 1;
		}
	}

	bool isLeap = isLeapYear(y);
	for (int i = 1; i < m; i++) {
		days += months[isLeap][i];
	}

	days += d;
	return (days % 7 + 4 - 1) % 7;
}

// 解析月份和星期，将字符串形式转换为数字形式
int parseMonthAndWeek(string str) {
	if (isDigit(str)) {
		return stoi(str);
	}
	return monthAndWeekMap[toLowerCase(str)];
}

// 解析输入的配置信息
void parseConfig(string crontab[]) {
	for (int i = 0; i < 5; i++) {
		// 当前类型的上下界
		int low = 0, high = 0;
		// 清空已有信息
		cfg[i].clear();
		// 处理星号(星号只能单独出现)
		if (crontab[i] == "*") {
			if (i == 0) { // 分钟
				high = 59;
			} else if (i == 1) { // 小时
				high = 23;
			} else if (i == 2) { // 月份中的天数
				low = 1;
				high = 31;
			} else if (i == 3) { // 月份
				low = 1;
				high = 12;
			} else { // 星期
				high = 6;
			}
			for (int j = low; j <= high; j++) {
				cfg[i].insert(j);
			}
			continue;
		}
		// 处理-和,
		string str = crontab[i];
		str = regex_replace(str, regex(","), " ");
		stringstream ss;
		ss << str;
		while (ss >> str) {
			int index = str.find("-");
			// 若不包含-
			if (index == string::npos) {
				cfg[i].insert(parseMonthAndWeek(str));
			} else {
				int start = parseMonthAndWeek(str.substr(0, index));
				int end = parseMonthAndWeek(str.substr(index + 1));
				while (start <= end) {
					cfg[i].insert(start++);
				}
			}
		}
	}
}

int main() {

	int n;
	long long s, t;
	cin >> n >> s >> t;

	string cmd, crontab[5];
	while (n--) {
		for (int i = 0; i < 5; i++) {
			cin >> crontab[i];
		}
		cin >> cmd;

		// 解析配置信息
		parseConfig(crontab);

		// 存储任务调度
		for (int y = s / HUNDRED_MILLION; y <= t / HUNDRED_MILLION; y++) {
			for (int m : cfg[3]) {
				for (int d : cfg[2]) {
					// 若d超过了y年m月的最大天数
					if (d > months[isLeapYear(y)][m]) {
						continue;
					}
					// 若y年m月d日的星期在day of week中
					if (find(cfg[4].begin(), cfg[4].end(), dayOfWeek(y, m, d))
							!= cfg[4].end()) {
						for (int h : cfg[1]) {
							for (int min : cfg[0]) {
								// 计算任务调度的时间
								long long date = (long long)y * HUNDRED_MILLION
										+ m * MILLION + d * 10000 + h * 100
										+ min;
								// 包含开始时间，不包含结束时间
								if (s <= date && date < t) {
									dict[date].push_back(cmd);
								}
							}
						}
					}

				}
			}
		}
	}

	// 输出
	for (map<long long, vector<string> >::iterator iter = dict.begin();
			iter != dict.end(); iter++) {
		for (string cmd : iter->second) {
			cout << iter->first << ' ' << cmd << endl;
		}
	}
	return 0;
}
  • Java版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;

public class Main {

	// 1亿
	public static final long HUNDRED_MILLION = 100000000L;

	// 1百万
	public static final long MILLION = 1000000L;

	public static final int[][] MONTHS = { { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 },
			{ 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 } };

	// 将字符串形式的月份（星期）映射为数字形式
	public static Map<String, Integer> monthAndWeekMap = new HashMap<>();

	public static Map<Long, List<String>> resultMap = new TreeMap<>();

	static {
		monthAndWeekMap.put("jan", 1);
		monthAndWeekMap.put("feb", 2);
		monthAndWeekMap.put("mar", 3);
		monthAndWeekMap.put("apr", 4);
		monthAndWeekMap.put("may", 5);
		monthAndWeekMap.put("jun", 6);
		monthAndWeekMap.put("jul", 7);
		monthAndWeekMap.put("aug", 8);
		monthAndWeekMap.put("sep", 9);
		monthAndWeekMap.put("oct", 10);
		monthAndWeekMap.put("nov", 11);
		monthAndWeekMap.put("dec", 12);
		monthAndWeekMap.put("sun", 0);
		monthAndWeekMap.put("mon", 1);
		monthAndWeekMap.put("tue", 2);
		monthAndWeekMap.put("wed", 3);
		monthAndWeekMap.put("thu", 4);
		monthAndWeekMap.put("fri", 5);
		monthAndWeekMap.put("sat", 6);
	}

	// 一行配置
	static class Config {
		Set<Integer> minutes;
		Set<Integer> hours;
		Set<Integer> dayOfMonth;
		Set<Integer> month;
		Set<Integer> command;
		Set<Integer> dayOfWeek;
	}

	// 是否为闰年
	public static boolean isLeapYear(int year) {
		return year % 400 == 0 || (year % 4 == 0 && year % 100 != 0);
	}

	// 计算y年m月d日是星期几，已知1970年1月1日是星期四
	public static int dayOfWeek(int y, int m, int d) {
		int days = 0;
		for (int i = 1970; i < y; i++) {
			days += 365;
			if (isLeapYear(i)) {
				days += 1;
			}
		}

		boolean isLeap = isLeapYear(y);
		for (int i = 1; i < m; i++) {
			days += MONTHS[isLeap ? 1 : 0][i];
		}

		days += d;
		return (days % 7 + 4 - 1) % 7;
	}

	// 判断字符串是否为数字
	public static boolean isDigit(String str) {
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) < '0' || str.charAt(i) > '9') {
				return false;
			}
		}
		return true;
	}

	// 解析月份和星期，将字符串形式转换为数字形式
	public static int parseMonthAndWeek(String str) {
		if (isDigit(str)) {
			return Integer.parseInt(str);
		}
		return monthAndWeekMap.get(str.toLowerCase());
	}

	// 解析输入的配置信息
	public static Config parseConfig(String[] crontab) {
		Config cfg = new Config();
		cfg.minutes = parseConfig0(crontab, 0);
		cfg.hours = parseConfig0(crontab, 1);
		cfg.dayOfMonth = parseConfig0(crontab, 2);
		cfg.month = parseConfig0(crontab, 3);
		cfg.dayOfWeek = parseConfig0(crontab, 4);
		return cfg;
	}

	private static Set<Integer> parseConfig0(String[] crontab, int i) {
		// 当前类型的上下界
		int low = 0, high = 0;
		Set<Integer> list = new HashSet<>();
		// 处理星号(星号只能单独出现)
		if ("*".equals(crontab[i])) {
			if (i == 0) { // 分钟
				high = 59;
			} else if (i == 1) { // 小时
				high = 23;
			} else if (i == 2) { // 月份中的天数
				low = 1;
				high = 31;
			} else if (i == 3) { // 月份
				low = 1;
				high = 12;
			} else { // 星期
				high = 6;
			}
			for (int j = low; j <= high; j++) {
				list.add(j);
			}
			return list;
		}
		// 处理-和,
		String[] sArr = crontab[i].split(",");
		for (int j = 0; j < sArr.length; j++) {
			int index = sArr[j].indexOf("-");
			// 若不包含-
			if (index == -1) {
				list.add(parseMonthAndWeek(sArr[j]));
			} else {
				int start = parseMonthAndWeek(sArr[j].substring(0, index));
				int end = parseMonthAndWeek(sArr[j].substring(index + 1));
				while (start <= end) {
					list.add(start++);
				}
			}
		}
		return list;
	}

	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		long s = scan.nextLong();
		long t = scan.nextLong();

		String[] crontab = new String[5];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < crontab.length; j++) {
				crontab[j] = scan.next();
			}
			String cmd = scan.next();

			// 解析配置信息
			Config cfg = parseConfig(crontab);

			for (int y = (int) (s / HUNDRED_MILLION); y <= t / HUNDRED_MILLION; y++) {
				for (int m : cfg.month) {
					for (int d : cfg.dayOfMonth) {
						// 若d超过了y年m月的最大天数
						if (d > MONTHS[isLeapYear(y) ? 1 : 0][m]) {
							continue;
						}
						// 若y年m月d日的星期在day of week中
						if (cfg.dayOfWeek.contains(dayOfWeek(y, m, d))) {
							for (int h : cfg.hours) {
								for (int min : cfg.minutes) {
									// 计算任务调度的时间
									long date = (long) y * HUNDRED_MILLION + m * MILLION + d * 10000 + h * 100 + min;
									// 包含开始时间，不包含结束时间
									if (s <= date && date < t) {
										if (!resultMap.containsKey(date)) {
											List<String> cmds = new ArrayList<>();
											cmds.add(cmd);
											resultMap.put(date, cmds);
										} else {
											resultMap.get(date).add(cmd);
										}
									}
								}
							}
						}

					}
				}
			}
		}

		scan.close();

		// 输出
		resultMap.forEach((date, cmds) -> {
			for (String cmd : cmds) {
				System.out.println(date + " " + cmd);
			}
		});
	}
}

----------本文结束感谢您的阅读----------
坚持原创技术分享，您的支持将鼓励我继续创作！