华为OD刷题流水账(4)

最小的调整次数(100)

题目描述:

有一个特异性的双端队列,该队列可以从头部或尾部添加数据,但是只能从头部移出数据。

小A依次执行2n个指令往队列中添加数据和移出数据。其中n个指令是添加数据(可能从头部添加、也可能从尾部添加),依次添加1到n;n个指令是移出数据。现在要求移除数据的顺序为1到n。为了满足最后输出的要求,小A可以在任何时候调整队列中数据的顺序。

请问 小A 最少需要调整几次才能够满足移除数据的顺序正好是1到n;

输入描述:

第一行一个整数 n,表示数据范围。

接下来有 2n 行,其中有 n 行为添加数据:指令“ head add x”表示从头部添加数据x,“ tail add x”表示从尾部添加数据x;另外 n 行为移出数据指令,指令为 “remove” 的形式,表示移出1个数据;1 ≤ n ≤ 3 * 10^5。

所有的数据均合法。

输出描述:

一个整数,表示 小A 要调整的最小次数。

补充说明:

输入会保证按照1到n的顺序加入队列。确保输出时对应的数据已经在队列中。

示例1:

输入:

3

head add 1

remove

tail add 2

head add 3

remove

remove

输出:

1

说明:


上图展示了所给用例的执行过程。其中,第一次remove,不需要调整,可以直接满足输出要求;第二次remove命令执行时,需要调整队列中元素的位置,将2调整到最前面,才可以满足输出的要求。这个调整可以任何时候进行,可以调整成任何顺序。


网上商城优惠活动(100)

题目描述:

【背景】

某网上商城举办优惠活动,发布了满减、打折、无门槛3种优惠券,分别为:

1.每满100元优惠10元,无使用数限制,如100~199元可以使用1张减10元,200~299可使用2张减20元,以此类推;

2.92折券,1次限使用1张,如100元,则优惠后为92元;

3.无门槛5元优惠券,无使用数限制,直接减5元。

【优惠券使用限制】

每次最多使用2种优惠券,2种优惠可以叠加(优惠叠加时以优惠后的价格计算),以购物200元为例,可以先用92折券优惠到184元,再用1张满减券优惠10元,最终价格是174元,也可以用满减券2张优惠20元为180元,再使用92折券优惠到165(165.6 向下取整)元,不同使用顺序的优惠价格不同,以最优惠价格为准。在一次购物中,同一类型优惠券使用多张时必须一次性使用,不能分多次拆开穿插使用(不允许先使用1张满减券,再用打折券,再使用一张满减券)。

【问题】

请设计实现一种解决方法,帮助购物者以最少的优惠券获得最优的优惠价格。优惠后价格越低越好,同等优惠价格,使用的优惠券越少越好,可以允许某次购物不使用优惠券。

【约定】

优惠活动每人只能参加一次,每个人的优惠券种类和数量是一样的。

输入描述:

第一行:每个人拥有的优惠券数量(数量取值范围为[0, 10]),按满减、打折、无门槛的顺序输入。

第二行:表示购物的人数n(1 <= n <= 10000)。

最后n行:每一行表示某个人优惠前的购物总价格(价格取值范围(0, 1000],都为整数)。

约定:输入都是符合题目设定的要求的。

输出描述:

每行输出每个人每次购物优惠后的最低价格以及使用的优惠券总数量,每行的输出顺序和输入的顺序保持一致。

补充说明:

1.优惠券数量都为整数,取值范围为[0, 10]。

2.购物人数为整数,取值范围为[1, 10000]。

3.优惠券的购物总价为整数,取值范围为(0, 1000]。

4.优惠后价格如果是小数,则向下取整,输出都为整数。

示例1:

输入:

3 2 5

3

100 

200

400

输出:

65 6

155 7

338 4

说明:

【输入说明】

第一行:3种优惠券数量分别为满减券3张,打折券2张,无门槛5张

第二行:总共3个人购物

第三行:第一个人购物优惠前价格为100元

第四行:第二个人购物优惠前价格为200元

【输出说明】

输入3个人,输出3行结果,同输入的顺序,对应每个人的优惠结果,如下:

第一行:先使用1张满减券优惠到90元,再使用5张无门槛券优惠25元,最终价格是65元,总共使用6张优惠券

第二行:先使用2张满减券优惠到180元,再使用5张无门槛券优惠25元,最终价格是155元,总共使用7张优惠券

第三行:先使用1张92折券优惠到368元,再使用3张满减券优惠30元,最终价格是338元,总共使用4张优惠券


计算至少需要多少个快递主站点(200)

题目描述:

快递业务范围有N个站点,A站点与B站点可以中转快递,则认为A-B站可达,如果A-B可达,B-C可达,则A-C可达。现在给N个站点编号0、1、…n-1,用s[i][j]表示i-j是否可达,s[i][j]=1表示i-j可达,s[i][j]=0表示i-j不可达。

现用二维数组给定N个站点的可达关系,请计算至少选择从几个主站点出发,才能可达所有站点(覆盖所有站点业务)。、

说明:s[i][j]与s[j][i]取值相同。

输入描述:

第一行输入为N,N表示站点个数。

之后N行表示站点之间的可达关系,第i行第j个数值表示编号为i和j之间是否可达。

输出描述:

输出站点个数,表示至少需要多少个主站点。

补充说明:

1<N<10000

示例1:

输入:

4

1 1 1 1

1 1 1 0

1 1 1 0

1 0 0 1

输出:

1

说明:

选择0号站点可以覆盖0、1站点,选择2号站点可以覆盖2号站点,选择3号站点可以覆盖3号站点,所以至少选择3个站点作为主站才能覆盖所有站点业务。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容