NYOJ 06 喷水装置（一）

描述

现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<Ri<15)的圆被湿润，这有充足的喷水装置i（1<i<600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。

输入

第一行m表示有m组测试数据
每一组测试数据的第一行有一个整数数n，n表示共有n个喷水装置，随后的一行，有n个实数ri，ri表示该喷水装置能覆盖的圆的半径。

输出

输出所用装置的个数

样例输入

2
5
2 3.2 4 4.5 6
10
1 2 3 1 2 1.2 3 1.1 1 2

样例输出

2
5

c 冒泡排序

#include<stdio.h>
#include<math.h>
int main()
{
    double e,g,h,m[650],n[650];
    int a,b,c,d,f;
    scanf("%d",&a);
    while(a--)
    {
        scanf("%d",&b);
        for(c=0;c<b;c++)
           {
               scanf("%lf",&n[c]);
               m[c]=sqrt(n[c]*n[c]-1);   //存放每个喷水装置在草坪上喷水的长度：
           }
        for(c=0;c<b-1;c++)
            for(d=0;d<b-c-1;d++)
            {
                if(m[d]<m[d+1])
                {
                    e=m[d];m[d]=m[d+1];m[d+1]=e;  //对喷水长度进行冒泡排序：
                }
            }
        f=1;g=0;
        for(c=0;c<b;c++)
        {
            g=g+m[c];    //喷水装置喷水长度相加：
            if(g<10)     //判断总的喷水长度是否大于10
                f++;
            else
                break;
        }
        printf("%d\n",f);
    }
    return 0;
}

c++ sort排序

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int main()
{
    double e,g,h,m[650],n[650];
    int a,b,c,d,f;
    scanf("%d",&a);
    while(a--)
    {
        scanf("%d",&b);
        for(c=0;c<b;c++)
           {
               scanf("%lf",&n[c]);
               m[c]=sqrt(n[c]*n[c]-1);   //存放每个喷水装置在草坪上喷水的长度：
           }
        sort(m,m+b);   //使用sort排序能节约时间避免超时
        f=1;g=0;
        for(c=b-1;c>=0;c--)   //sort排序默认从小到大
        {
            g=g+m[c];    //喷水装置喷水长度相加
            if(g<10)     //判断总的喷水长度是否大于10
                f++;
            else
                break;
        }
        printf("%d\n",f);
    }
    return 0;
}