OD C卷 - 小朋友来自多少小区

小朋友来自多少小区 (100)

• 每个小朋友报出与自己同一个小区的人数，存入数组garden中；
• 计算至少有几个小区？多少小朋友？
  输入描述：
  输入garden数组，如2 2 3， 即第一个小朋友报出有2个小朋友跟自己同一个小区，第二个小朋友同样报出2个，依次类推; garden数组长度最大为999；
  输出描述：
  至少的小区数，小朋友数

示例1
输入：
2 2 3
输出：
2，7

示例2
输入：
2 2 2 2 2 3 3
输出：
3,10

思路：

• 贪心算法，依次遍历，让尽可能多的小朋友在同一个小区；
  • garden 升序排序；
  • 初始化 小区数areas=1, friend_nums = garden[0]+1，dist= garden[0]
  • 从i=1开始遍历garden，for i in range(1, len(garden)): 如果当前报数与前一个报数相同，则判断能否算入同一个小区；
    • 是，则dist-=1，继续下一次遍历；
    • 否，则areas += 1, friend_nums += garden[i] +1, dist=garden[i]
  • 输出areas,friend_nums

class GardenNum:def solution(self, garden):# 排序garden.sort()# 初始化areas = 1friend_nums = garden[0] + 1dist = garden[0]for i in range(1, len(garden)):if garden[i] == garden[i-1]: # 可能是同一个小区if dist > 0:# 算入同一个小区dist -= 1else:areas += 1 #friend_nums += garden[i] + 1dist = garden[i]else:# 报数与前一个不同，肯定不是同一个小区areas += 1  #friend_nums += garden[i] + 1dist = garden[i]print(areas, end=",")print(friend_nums)if __name__ == '__main__':garden_num = GardenNum()while True:try:garden = list(map(int, input().strip().split()))garden_num.solution(garden)except KeyboardInterrupt:break

其他基于索引的实现：

nums = [int(x) for x in input().split(" ")]
#index为报告的结果，zones[index]为报告相同结果的总人数
zones = [0 for x in range(1000)]
count = 0i=0
while(True):if(i>=len(nums)):breakelse:zones[nums[i]]+=1i+=1for j in range(1000):if (zones[j] <= 0):continueelse:total = math.ceil(zones[j] / (j+1));count += total * (j+1);
print(count);