标题:贪心算法求着喷水装置问题。
只看楼主
花脸
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:9
帖 子:788
专家分:907
注 册:2017-1-4
结帖率:95.37%
已结贴  问题点数:20 回复次数:2 
贪心算法求着喷水装置问题。
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

bool cmp(double a,double b)
{
    return a>b;
}

int main()
{
    int m,n,i,count;
    double a[600];
    cin>>m;
    while(m--)
    {
        double sum=0,len=0;
        count=0;
        cin>>n;
        for(i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n,cmp);
        for(i=0;i<n;)
        {
            a[i++];
            len+=2*sqrt(a[i]*a[i]-1);
            count++;
            if(len>=20)
                break;
        }
        cout<<count<<endl;
    }
    return 0;
}

运行结果总是不正确。
题目:
现有一块草坪,长为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
搜索更多相关主题的帖子: 贪心 double count cin 一行 
2017-11-26 00:25
炎天
Rank: 13Rank: 13Rank: 13Rank: 13
来 自:桃花岛
等 级:贵宾
威 望:29
帖 子:1218
专家分:4986
注 册:2016-9-15
得分:20 
运行结果总是不正确,
那你输入的样例是什么,让别人去猜么?

程序代码:
for (i = 0; i<n;)
{
            
    len += 2 * sqrt(a[i] * a[i] - 1);
    a[i++];           //,若自加运算在for循环里 例如for( ;  ; i++/++i),直到一次for循环结束才完成真正自加。 若在分号前面 例如 i++;  分号结束完成自加运算 。
    count++;
    if (len >= 20)
          break;
}


[此贴子已经被作者于2017-11-26 12:52编辑过]


早知做人那么辛苦!  当初不应该下凡
2017-11-26 12:48
花脸
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:9
帖 子:788
专家分:907
注 册:2017-1-4
得分:0 
回复 2楼 炎天
恩 明白了 谢谢
2017-11-26 13:32



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-482825-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.458569 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved