航班时间
来源： 第九届蓝桥杯省赛C++A组,第九届蓝桥杯省赛JAVAA组
题目要求
题目描述：
小 h 前往美国参加了蓝桥杯国际赛。
小 h hh 的女朋友发现小 h 上午十点出发，上午十二点到达美国，于是感叹到“现在飞机飞得真快，两小时就能到美国了”。
小 h 对超音速飞行感到十分恐惧。
仔细观察后发现飞机的起降时间都是当地时间。
由于北京和美国东部有 12 小时时差，故飞机总共需要 14 小时的飞行时间。
不久后小 h 的女朋友去中东交换。
小 h 并不知道中东与北京的时差。
但是小 h 得到了女朋友来回航班的起降时间。
小 h 想知道女朋友的航班飞行时间是多少。
对于一个可能跨时区的航班，给定来回程的起降时间。
假设飞机来回飞行时间相同，求飞机的飞行时间。
输入格式：
一个输入包含多组数据。
输入第一行为一个正整数 T ，表示输入数据组数。
每组数据包含两行，第一行为去程的起降时间，第二行为回程的起降时间。
起降时间的格式如下:
第一种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间当日h2时m2分s2秒降落。
第二种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间次日h2时m2分s2秒降落。
第三种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间第三日h2时m2分s2秒降落。
输出格式：
对于每一组数据输出一行一个时间h h : m m : s s，表示飞行时间为h h 小时m m 分s s 秒。
注意，当时间为一位数时，要补齐前导零，如三小时四分五秒应写为03 : 04 : 05 。
数据范围：
保证输入时间合法（ 0 ≤ h ≤ 23 , 0 ≤ m , s ≤ 59 ），飞行时间不超过24 小时。
输入样例：
3
17:48:19 21:57:24
11:05:18 15:14:23
17:21:07 00:31:46 (+1)
23:02:41 16:13:20 (+1)
10:19:19 20:41:24
22:19:04 16:41:09 (+1)
输出样例：
04:09:05
12:10:39
14:22:05
思路分析
其实是一个数学类的题目，下面是公式推导：
去乘起飞时间+航行时间+时差=去乘降落时间 (公式一)
回程起飞时间+航行时间-时差=回程降落时间 (公式二)
求:是航行时间
已知:去乘起飞时间,回程起飞时间,去乘降落时间,回程降落时间
根据公式一+公式二:
去乘起飞时间+回程起飞时间+2*航行时间=去乘降落时间+回程降落时间
航行时间=(去乘降落时间-去乘起飞时间+回程降落时间-回程起飞时间)/2
再一个就是本题的读入是比较烦的，如何把一个字符串中的数字信息进行摘出，有如下代码：
sscanf(line.c_str(), "%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &d);
代码
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int get_seconds(int h, int m, int s) { return h * 3600 + m * 60 + s; } int get_time() { string line; getline(cin, line); //保持一致: if (line.back() != ')') line += "(+0)"; //把字符串中的数字信息读入到变量之中 int h1, m1, s1, h2, m2, s2, d; sscanf(line.c_str(), "%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &d); return get_seconds(h2, m2, s2) - get_seconds(h1, m1, s1) + d * 24 * 3600; } int main() { int T; scanf("%d", &T); getchar(); while (T -- ) { int time = (get_time() + get_time()) / 2; int hours = time / 3600; int minutes = time % 3600 / 60; int seconds = time % 60; printf("%02d:%02d:%02d\n", hours, minutes, seconds); } return 0; }
外卖店优先级
来源： 第十届蓝桥杯省赛C++A/C组,第十届蓝桥杯省赛JAVAA/B/C组
题目要求
题目描述：
“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ∼ N 。
每家外卖店都有一个优先级，初始时 (0 00 时刻) 优先级都为 0。
每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1 ，最低减到 0 ；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2 。
如果某家外卖店某时刻优先级大于 5 ，则会被系统加入优先缓存中；如果优先级小于等于 3 ，则会被清除出优先缓存。
给定 T时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优先缓存中。
输入格式：
第一行包含 3 个整数 N , M , T 。
以下 M 行每行包含两个整数 t s 和 i d ，表示 t s时刻编号 i d 的外卖店收到一个订单。
输出格式：
输出一个整数代表答案。
数据范围：
1≤N,M,T≤105,
1≤ts≤T,
1≤id≤N
输入样例：
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2
输出样例：
1
样例解释：
6 时刻时，1 号店优先级降到 3 ，被移除出优先缓存；2 号店优先级升到 6 ，加入优先缓存。
所以是有 1 家店 (2 号) 在优先缓存中。
思路分析
int j = i; while (j < m && order[j] == order[i]) j ++;
因为此时的 o r d e r 数组已经有序，上述代码的结果即 i ~ j − 1 的范围内的值都是相同的，即对于同一家外卖店在同一时刻有多个订单，即一共订单量为：cnt = j - i;，这家点的编号为：id = order[i].y;，时刻为：tm = order[i].x;，即当前的时刻是 t m ，现在我们要计算 t m 时刻之前(从 l a s t [ i d ] 到 t m − 1 t)的信息，对应代码：
score[id] -= tm - last[id] - 1; score[id] = max(0, score[id]); if (score[id] <= 3) st[id] = false;
然后再来考虑 t m这一时刻，即我们来计算此时的优先级，以及在获得了 j − i 个订单后店铺是否进入了优先缓存中，并更新 l a s t [ i d ] ：
score[id] += cnt * 2; if (score[id] > 5) st[id] = true; last[id] = tm;
最后，我们要计算在每个店铺获得了最后一个订单的时刻到最终的 t 时刻，需要让优先级减去多少，并计算是否让这些店铺退出优先缓存中：
for (int i = 1; i <= n; i ++ ) if (last[i] < t) { score[i] -= t - last[i]; if (score[i] <= 3) st[i] = false; }
最终只需要遍历一遍 s t 数组计算出最终的 r e s即可。
代码
#include <cstdio> #include <cstring> #include <algorithm> #define x first #define y second using namespace std; const int N = 100010; typedef pair<int, int> PII; PII order[N]; int last[N]; // 上一次的订单时间 int score[N]; // 店铺的优先级 bool st[N]; int main() { int n, m, t; scanf("%d%d%d", &n, &m, &t); for (int i = 0; i < m; i ++ ) scanf("%d%d", &order[i].x, &order[i].y); sort(order, order + m); for (int i = 0; i < m;) { int j = i; while (j < m && order[j] == order[i]) j ++; int cnt = j - i, id = order[i].y, tm = order[i].x; // 当前的时刻是tm,现在我们要计算tm时刻之前(从last[id]到tm-1)的信息 score[id] -= tm - last[id] - 1; score[id] = max(0, score[id]); if (score[id] <= 3) st[id] = false; // 现在处理t时刻的信息 score[id] += cnt * 2; if (score[id] > 5) st[id] = true; last[id] = tm; i = j; } for (int i = 1; i <= n; i ++ ) if (last[i] < t) { score[i] -= t - last[i]; if (score[i] <= 3) st[i] = false; } int res = 0; for (int i = 1; i <= n; i ++ ) if (st[i]) res ++; printf("%d\n", res); return 0; }
