CCF201712-3-Crontab
程序员文章站
2022-04-07 09:03:48
...
（一）题面：
样例输入
3 201711170032 201711222352
0 7 * * 1,3-5 get_up
30 23 * * Sat,Sun go_to_bed
15 12,18 * * * have_dinner
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
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.我们分析对比一下两种方法：
①对于第一种方法而言，由于输出不会超过10000行，说明将会发生的事件不会超过10000个，如果可以将所有会发生的事件给写出来，那么效率将会非常高。但是想一想怎么将一个事件所有的给定时间范围内的各个时间分呢。这个想想貌似不是那么好处理。
②对于第二种方法，如果给定了一个时间，只需要判断每个事件在这个时间点是否会发生就相对简单一些了，因为给定一个确切的时间和时间满足发生条件的时间，我们只要对二者进行对比即可。但是这里有问题是，对时间范围内的所有时间进行判定，这个时间复杂度似乎有点高，考虑一个极限范围：1970-01-01~2099-12-31，总共分钟数为（粗略计算）：130*365*24*60=68328000=7e7,再考虑对于每一分钟都需要判断所有的事件（<=20），我们可以粗略地得到运算次数在1.4e9。虽然题目给了十秒钟，但是依然有超时地风险。即使如此，没有想到更好地解决方法，索性就先试试看，不过还好没有超时。
3.这个题目如果在赛场上没有太多的时间思考，那么根据题中测试样例的限定条件去写代码得分，也是一种不错的选择。
（四）具体代码：
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<map>
#include<algorithm>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int WEEK[2101][15][35];
bool Is_leap_year(int year){return (year%4==0&&year%100!=0)||(year%400==0);}
int Day_of_month[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>Mp_Month;
map<string,int>Mp_Week;
void init(){ //打标，计算某年某月某日是学期几
Mp_Month["jan"]=1;Mp_Month["feb"]=2;Mp_Month["mar"]=3;Mp_Month["apr"]=4;Mp_Month["may"]=5;Mp_Month["jun"]=6;
Mp_Month["jul"]=7;Mp_Month["aug"]=8;Mp_Month["sep"]=9;Mp_Month["oct"]=10;Mp_Month["nov"]=11;Mp_Month["dec"]=12;
Mp_Week["sun"]=0;Mp_Week["mon"]=1;Mp_Week["tue"]=2;Mp_Week["wed"]=3;Mp_Week["thu"]=4;Mp_Week["fri"]=5;Mp_Week["sat"]=6;
WEEK[1970][1][1]=4;
int year=1970;
while(year<2101){
int month=1;
while(month<13){
int day=1;
while(day<=Day_of_month[Is_leap_year(year)][month]){
WEEK[year][month][++day]=(WEEK[year][month][day-1]+1)%7;
}
WEEK[year][++month][1]=(WEEK[year][month-1][Day_of_month[Is_leap_year(year)][month-1]]+1)%7;
}
WEEK[++year][1][1]=(WEEK[year-1][12][31]+1)%7;
}
}
void Deal_with_str(string &str){ //处理一下输入中的星期和月份是英文缩写的情况
int len=str.length();
string mid1="",mid2="";
for(int i=0;i<len;i++){
if(str[i]>='A'&&str[i]<='Z')str[i]+=32;
if((str[i]>='0'&&str[i]<='9')||str[i]==','||str[i]=='-'||str[i]=='*'){mid1+=str[i];continue;}
while(i<len&&(str[i]>='a'&&str[i]<='z')){mid2+=str[i];i++;if(str[i]>='A'&&str[i]<='Z')str[i]+=32;}
int m=Mp_Month[mid2];
if(!m)m=Mp_Week[mid2];
if(m<10)mid1+=m+'0';
else mid1+=m/10+'0',mid1+=m%10+'0';
mid2="";
i--;
}
str=mid1;
}
struct Cmd{ //保存事件的结构体
string Thing;
int day_of_week[8];
int month[13];
int day_of_month[32];
int hours[25];
int minutes[60];
}All_cmd[21];
struct Time{ //处理时间的结构体
int Year,Month,Day,Hours,minutes;
void Set_time(LL num){
minutes=num%100;num/=100;
Hours=num%100;num/=100;
Day=num%100;num/=100;
Month=num%100;num/=100;
Year=num;
}
void Prt(){
printf("%04d%02d%02d%02d%02d \n",Year,Month,Day,Hours,minutes);
}
void Add(){
minutes++;
if(minutes==60){minutes=0;Hours++;
if(Hours==24){Hours=0;Day++;
if(Day>Day_of_month[Is_leap_year(Year)][Month]){Day=1;Month++;
if(Month==13){Month=1;Year++;
}
}
}
}
}
bool operator < ( const Time &T1)const{
if(Year!=T1.Year)return Year<T1.Year;
if(Month!=T1.Month)return Month<T1.Month;
if(Day!=T1.Day)return Day<T1.Day;
if(Hours!=T1.Hours)return Hours<T1.Hours;
return minutes<T1.minutes;
}
}Beg,End,test;
void Get_info(string str,int info[]){ //处理每一个事件的各个时间信息
int len=str.length();
if(str=="*")info[0]=INF; //INF表示该项参数无要求
else
for(int i=0;i<len;){
int t1=0;
while(i<len&&str[i]>='0'&&str[i]<='9'){t1=t1*10+(str[i]-'0');i++;}
if(str[i]=='-'){
int t2=0;i++;
while(i<len&&str[i]>='0'&&str[i]<='9'){t2=t2*10+(str[i]-'0');i++;}
for(int t=t1;t<=t2;t++)info[t]=1;
i++;
}
else{
info[t1]=1;i++;
}
}
}
int main(){
freopen("in.txt","r",stdin);
init();
int n;
string str;
LL Data_beg,Data_end;
cin>>n>>Data_beg>>Data_end;
Beg.Set_time(Data_beg);
End.Set_time(Data_end);
for(int p=0;p<n;p++){
cin>>str;Get_info(str,All_cmd[p].minutes);
cin>>str;Get_info(str,All_cmd[p].hours);
cin>>str;Get_info(str,All_cmd[p].day_of_month);
cin>>str;Deal_with_str(str);
Get_info(str,All_cmd[p].month);
cin>>str;Deal_with_str(str);
Get_info(str,All_cmd[p].day_of_week);
cin>>All_cmd[p].Thing;
}
while(Beg<End){
for(int i=0;i<n;i++){ //判断这一分钟有哪些事件发生
if((All_cmd[i].day_of_week[0]==INF||All_cmd[i].day_of_week[WEEK[Beg.Year][Beg.Month][Beg.Day]]==1)
&&(All_cmd[i].month[0]==INF||All_cmd[i].month[Beg.Month]==1)
&&(All_cmd[i].day_of_month[0]==INF||All_cmd[i].day_of_month[Beg.Day]==1)
&&(All_cmd[i].hours[0]==INF||All_cmd[i].hours[Beg.Hours]==1)
&&(All_cmd[i].minutes[0]==INF||All_cmd[i].minutes[Beg.minutes]==1)){
printf("%04d%02d%02d%02d%02d ",Beg.Year,Beg.Month,Beg.Day,Beg.Hours,Beg.minutes);
cout<<All_cmd[i].Thing<<endl;
}
}
Beg.Add();
}
return 0;
}
（五）总结：理清思路，注意细节。
推荐阅读