题目
鲨鱼巨巨2.0（以下简称小鲨鱼）以优异的成绩考入了51nod小学。并依靠算法方面的特长，在班里担任了许多职务。每一个职务都有一个起始时间A和结束时间B，意为小鲨鱼在[A, B]时间内，担任了某职务(inclusively)。
现在给定小鲨鱼的职务履历表，你可以高效的给出小鲨鱼在某天担任了哪些职务吗？
p.s. 由于小鲨鱼担任的职务太多，所有任期小于一个自然月的职务都忽略不计。（如1月1日~2月1日为一个自然月，即月份加1）
p.p.s. 输入数据保证小鲨鱼同时不担任超过200种职务。（牛！）
p.p.p.s 输入的日期均为合法日期，范围在2000年01月01日~2999年12月31日。
p.p.p.p.s巨大的输入输出，推荐使用scanf/printf，编译器推荐使用Virtual C++Input
第一行为一个整数n，代表小鲨鱼担任过N种职务。(1<=n<=10^5)接下来的n行，每一行为七个整数，y0,m0,d0,y1,m1,d1,x。意为在<y0,m0,d0>到<y1,m1,d1>时间内，小鲨鱼担任了职务x。(1<=x<=10^9)给定的时间皆合法，且起始日期小于或等于截止日期。职务x是唯一的。接下来是一个整数q，代表q次查询。(1<=q<=10^4)接下来的q行，每一行为三个整数<y,m,d>，代表查询的日期。时间皆合法。
Output
每一次查询输出一行结果。首先输出一个整数n，代表此时小鲨鱼担任的职务数。（n可以为0）接下来是n个整数，代表小鲨鱼担任的职务。职务列表保持升序。
Input示例
4200001012000010111120000102200102220000128200002293332000012920000228444420000101200001022000012820000229
Output示例
0122222223332222333
思路：
开始还考虑一下二分，发现直接暴力就ok了,这里排了下序，稍微优化了一下； 主要是判断自然月有点绕，如果年份不同肯定可以，如果年份相同，月份差一，那么天只要前小于等于后者就行；否则月份差2以上也是自然月；代码：
#include<iostream>#include<vector>#include<algorithm>#include<cstdio>using namespace std;typedef struct DATE{int s;int e;int w;bool is_invalid;DATE(int y0,int m0, int d0, int y1, int m1, int d1,int r){is_invalid = true;if (y0 < y1 || (y0 == y1 && (m1-m0)>1) ||(y0 == y1 && (m1-m0)==1 && d0 <= d1) ){is_invalid = false;}s = y0*10000+m0*100+d0;e = y1*10000+m1*100+d1;w = r;}}Date;vector<Date>dates;bool cmp(const Date &a, const Date &b){return a.s < b.s;}//int b_search(int v, int n)//{// int low = 0;// int high = n - 1;// while(low <= high)// {// int mid = low + (high-low)/2;// if (dates[mid].s >)// }//}//Date d[100005];int main(){int n,q;scanf("%d", &n);int y0,m0,d0,y1,m1,d1,r;dates.reserve(n+1);for (int i = 0; i < n; ++ i){scanf("%d %d %d %d %d %d %d", &y0,&m0,&d0,&y1,&m1,&d1,&r);Date date(y0,m0,d0,y1,m1,d1,r);if (!date.is_invalid){dates.push_back(date);}}sort(dates.begin(),dates.end(),cmp);scanf("%d", &q);int y,m,d;for (int i= 0; i < q; ++ i){// int pos = 0;scanf("%d %d %d", &y,&m,&d);//pos = b_search(y*10000+m*100+d, dates.size());int v = y*10000+m*100+d;vector<int>res;res.reserve(n);for (int j = 0; j < dates.size(); ++ j){if (v < dates[j].s){break;}if (v >= dates[j].s && v <= dates[j].e){res.push_back(dates[j].w);}}sort(res.begin(),res.end());if (res.size() == 0){printf("0\n");}else{printf ("%d", res.size());for (int j = 0; j < res.size(); ++ j){printf(" %d", res[j]);}printf("\n");}}return 0;}
如果觉得《nod-1631-小鲨鱼在51nod小学》对你有帮助，请点赞、收藏，并留下你的观点哦！
