Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
英语四级考试临近了，小Y却发现他已经把以前学的单词几乎忘光了。好在现在离考试还有一段时间，小Y决定从现在开始夜以继日地背单词。也就是说小Y废寝忘食，一天二十四小时地背单词。 今天的日期(时间)是YYYY年mm月dd日hh时min分，考试的时间是YYYY’年mm’月dd’日hh’时min’分。这之间的所有时间小Y都用来背单词了，那么考试之前他最多能背多少个单词呢? 时间紧张，小Y只管数量不管质量。当然有的单词长一些，有的单词短一些。长的单词难背一些，短的单词好背一些。根据小Y的经验，他能一眼看出背某一个单词需要的时间，以分钟记。 现在给你一个字典，请你挑出最多的单词使小Y能在考试前背出来。
【输入格式】
第一行一个整数N，表示字典中的单词数，N<=5000。 接下来N行，每行一个整数表示背这个单词需要用的时间，以分钟记，小于等于10000。(这个单词本身是什么并不重要，不是吗?当前小Y已经认识的单词数为0个)。 接下来两行依次是当前时问和考试时间。时间给出的格式是:yyyy-mm-dd-hh:min.例如:2007-06-23-02:00，采用24小时制，每天从00:00-23:59，年份从0000到9999。
【输出格式】
一行一个数，表示考试前小Y最多能背出的单词数:
【数据规模】
Sample Input1
2
l
l
2007-06-23-11:59
2007-06-23-12:00
Sample Output1
1
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=u235
【题解】
先一年一年的加;
遇到闰年加366天(换算成分钟);
遇到平年加355天;
假设某一年x是闰年；需满足
x%4 == 0 && (x%100!=0 || (x%100==0 && x%400==0));
之后就一分钟一分钟地加就好;
每次模拟一下进位就好;
这样就能处理出两个时间的间隔分钟;
然后把所有的单词的时间升序排；
从小到大枚举；遇到可以背的就背;(价值都是一样的，那就选价格最小的先背肯定最优)
闰年2月是29天，平年28天；
1 3 5 7 8 10 12是31天
4 6 9 11是30天
【完整代码】
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXN = 5000+100;
struct abc
{
int year,month,day,hour,minute;
};
int n;
int a[MAXN];
abc ks,js;
LL rest;
int day[13];
bool rn(int x)
{
if (!(x%4))
{
if (x%100)
return true;
else
{
if (x%400)
return false;
else
return true;
}
}
else
return false;
}
void change(abc &ks)
{
if (ks.minute>59)
{
ks.minute=0;
ks.hour++;
if (ks.hour == 24)
{
ks.hour=0;
ks.day++;
if (ks.day > day[ks.month])
{
ks.day = 1;
ks.month++;
if (ks.month > 12)
{
ks.year++;
ks.month = 1;
}
}
}
}
}
int main()
{
// freopen("F:\rush.txt","r",stdin);
scanf("%d",&n);
for (int i = 1;i <= n;i++)
scanf("%d",&a[i]);
scanf("%d-%d-%d-%d:%d",&ks.year,&ks.month,&ks.day,&ks.hour,&ks.minute);
scanf("%d-%d-%d-%d:%d",&js.year,&js.month,&js.day,&js.hour,&js.minute);
rest = 0;
for (int i = ks.year+1;i <= js.year-1;i++)
if (rn(i))
rest+=527040;
else
rest+=525600;
day[1] = day[3] = day[5] = day[7] = day[8] = day[10] = day[12] = 31;
day[4] = day[6] = day[9] = day[11] = 30;
if (ks.year<js.year)
{
int goal = ks.year+1;
if (rn(ks.year))
day[2] = 29;
else
day[2] = 28;
while (ks.year<goal)
{
ks.minute++;
rest++;
change(ks);
}
ks.year = js.year;
if (rn(ks.year))
day[2] = 29;
else
day[2] = 28;
while (ks.month < js.month || ks.day < js.day || ks.hour < js.hour || ks.minute < js.minute)
{
rest++;
ks.minute++;
change(ks);
}
}
else
if (ks.year == js.year)
{
if (rn(ks.year))
day[2] = 29;
else
day[2] = 28;
while (ks.month < js.month || ks.day < js.day || ks.hour < js.hour || ks.minute < js.minute)
{
rest++;
ks.minute++;
change(ks);
}
}
sort(a+1,a+1+n);
int num = 0;
for (int i = 1;i <= n;i++)
if (a[i] <= rest)
rest-=a[i],num++;
else
break;
printf("%d
",num);
return 0;
}