[CSP-S 2019 江西] 日期

知识点

枚举、字符串、日期处理

解题思路

枚举平年的每个合法月日，格式化为MM-DD，与输入按位比较，取最少不同字符数。

正确性说明

任何最终合法日期都在365个枚举目标中。变为某目标恰需修改不同的数字位置，因此对所有合法目标取最小值就是全局最优。

易错点

2月固定28天，不允许02-29；保留前导零；月份或日期为00、99时仍参与正常比较。

复杂度

固定枚举365天，每次比较5位，时间和额外空间均为O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);string s;cin>>s;int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31},ans=4;for(int m=1;m<=12;m++)for(int d=1;d<=days[m];d++){char t[6];snprintf(t,6,"%02d-%02d",m,d);int z=0;for(int i=0;i<5;i++)z+=s[i]!=t[i];ans=min(ans,z);}cout<<ans<<'\n';}