在ACM程序设计竞赛赛场,每个队伍每正确解答一道题目后就会在其前面升起1个彩色气球。为了增加比赛的气氛,也为了选拔优秀选手参加5月份的省赛,所以,我们也来让气球升起来吧。估计题目的难度并结合实际,需要购买8种不同颜色的气球。每种颜色的气球只能用于一道题目上,所以气球不能相互替代。现在告诉你上面所说的各色气球需要的个数,对应各色气球现在已有的气球个数,请你统计总共还要购买多少个气球。 输入格式: 测试数据有多组,先输入测试组数T(1<=T<=20)。然后输入T组测试数据。 每组测试的第一行是8种各色气球需要的个数(都是小于1000的正整数),第二行是8种各色气球已有的个数(都是小于1000的正整数)。 输出格式: 对于每组测试,在一行上输出还需要购买的气球总数。
时间: 2023-06-20 09:09:34 浏览: 426
ACM程序设计大赛\ACM试题训练
题目描述
在ACM程序设计竞赛赛场,每个队伍每正确解答一道题目后就会在其前面升起1个彩色气球。为了增加比赛的气氛,也为了选拔优秀选手参加5月份的省赛,所以,我们也来让气球升起来吧。估计题目的难度并结合实际,需要购买8种不同颜色的气球。每种颜色的气球只能用于一道题目上,所以气球不能相互替代。现在告诉你上面所说的各色气球需要的个数,对应各色气球现在已有的气球个数,请你统计总共还要购买多少个气球。
输入格式:
测试数据有多组,先输入测试组数T(1<=T<=20)。然后输入T组测试数据。
每组测试的第一行是8种各色气球需要的个数(都是小于1000的正整数),第二行是8种各色气球已有的个数(都是小于1000的正整数)。
输出格式:
对于每组测试,在一行上输出还需要购买的气球总数。
样例输入
2
10 2 4 3 6 7 7 5
6 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
样例输出
27
8
算法1
(暴力枚举) $O(n)$
根据题目所说,每种颜色的气球只能用于一道题目上,所以气球不能相互替代。因此,对于每种颜色的气球,需要买的数量等于需要的数量减去已经有的数量。
时间复杂度
每组数据需要遍历8次,因此时间复杂度为$O(8T)$,即$O(T)$。
空间复杂度
只需要常数个变量,空间复杂度为$O(1)$。
C++ 代码
算法2
(暴力枚举) $O(n)$
blablabla
时间复杂度
blablabla
空间复杂度
blablabla
C++ 代码
阅读全文