GCJ Qualification Round 2015 题解

前言

这篇日志用中文写是因为想省点时间打游戏。。。(请鄙视我吧。。。

A. Standing Ovation

题意

这是一个骗掌声的故事。

当演出结束后,观众们要站起来鼓掌。但是有些观众比较羞涩,只有在k个人站起来鼓掌后才会故障。

你的目标是在观众中安插一些卧底领掌,让所有观众都站起来鼓掌。(臭不要脸)

求最少的卧底数。

数据规模

抛开数据规模谈解题,都是TM耍流氓。 —— Wizmann

100组数据。

小数据集,观众羞涩值的范围:0 ≤ Smax ≤ 6.

大数据集,观众羞涩值的范围:0 ≤ Smax ≤ 1000.

解题

本题比较简单。有两种方法,一是暴力枚举,因为大数据集中,观众羞涩值最大只为1000,即最大安插卧底数不超过1000。(当然,二分也可以,不过对于1000的数据集,真心没啥必要。)

二是O(N)的一个遍历,在观众羞涩的不想鼓掌时,安插相应数量的卧底。

本题推荐方法一。因为个人感觉,在编程竞赛中 …

more ...