吐槽
滚动

2017 C语言积分赛 周赛一 A题 我们fgo玩家是这样的 题解

题目描述

小辉最近沉迷于玩手机游戏,不仅玩,而且他还同时玩很多个。然而在元旦一天,所有的手机游戏在那一阵都有活动。而且由于他玩的游戏比较多,所有一共可能有几万个活动【你就不能少玩一点手游吗(╯°□°)╯︵ ┻━┻】 因为活动时间有重叠,他不能同时打2个活动,也不能中途放弃活动。所以他把自己所有的活动都列了出来,每个活动的起始时间和终止时间做成纯整数字的形式【所以说为什么是纯数字啊(╯°□°)╯︵ ┻━┻】,请聪明的同学们帮忙看看小辉至少会错过多少个活动

输入

1、 活动终止时间永远大于该活动的起始时间。所有活动用”[”和”]”包起来,并且整合在一个”[“和”]”中,活动之间也用逗号隔开,如:[[0,6,],[10,12]]。 2、 像[5,6]和[6,7]这样的2个活动,虽然时间接在一起,但是不会互相重叠。 3、 所有数据不大于2147483647 (int的最大范围)

4.活动最多10,000个

输出

输出小序至少会错过的活动数目

样例输入

样例输出

可贪心可DP,这里介绍DP写法。

思路:

1、先按结束时间排序,再在相同的结束时间区间内按开始时间排序。

2、因为此时已经严格有序,所以每次寻找结束时间离当前活动开始时间最近的活动。

状态转移方程:f[t[i]]=maxn(f[t[i-1]],f[t[temp]]+1);

Code:

 

dp
Contents licensed under Creative Commons by-nc-sa 3.0.
Post Comment

Post Comment