喷水装置［贪心法］

喷水装置

有一块草坪，长为l，宽为w，在它的中心线上不同位置处装有n(n<=10000)个点状的喷水装置。每个喷水装置i喷水的效果会让以它为中心，半径为ri的圆形区域湿润。请选择尽量少的喷水装置，把整个草坪全部湿润。

解题思路：
从头开始选择喷水的位置，ri应该是圆心到圆形区域和草坪边界交点的距离。运用贪心法使每一个喷水装置的作用区域尽量大，这样用的喷水装置个数就会为最少。

翻硬币［穷举法］

翻硬币

考虑有一个翻硬币的游戏。有N(N<=10000)行硬币，每行有9个硬币，排成一个N＊9的方阵。有的硬币正面朝上，有的硬币反面朝上。我们每次可以把一整行或一整列的硬币翻过来，请问怎么翻，使得正面朝上的硬币尽量多。

解题思路
用二维数组模拟硬币方阵，或者用两个一行和一列的一维数组统计本行或本列正面向上的硬币个数，压缩空间占用。分别按行和列扫描，当正面朝上的个数小于本行或列总数的一半时，作翻硬币处理，如果不满足这个条件则不做处理。任意一行或列被处理后，需要重新统计正面朝上的硬币个数。直到所有行或列都不满足处理的条件，程序结束。

还应进一步考虑行或列处理后对于其他行列的影响，达到最大限度的使正面朝上～～

售票员［穷举法］

售票员

某城市有很多公共汽车，因此也有很多当地居民当上了售票员。如果在所有的市民中，售票员的人数超过了P％而不到Q％，那么这个城市至少有多少市民呢？

入：P＝13 Q＝14.1
出：15

C代码：

#include < stdio.h >
#include < stdlib.h >
#include < math.h >

int main(int argc, char **argv)
{
 float p, q, once, temp;
 int max = 1, i;

 fscanf(stdin, "%g %g", &p, &q);
 p /= 100; q /= 100;

 while (1) {
  once = 1/(float)max;
  for (i = 0; i <= max; ++i) {
   temp = i * once;
   if (p < temp && q > temp) {
    fprintf(stdout, "%i\n", max);
    return 0;
   }
  }
  ++max;
 }

 return 0;
}