NYOJ-6:噴水装置(一)

噴水装置(一)
出典:NYOJ
ラベルラベル:ソート、欲張りアルゴリズム
参考資料:
類似タイトル:https://blog.csdn.net/wingrez/article/details/82012429
タイトル
従来の芝生は、長さが20メートル、幅が2メートルで、横中心線上に半径Riの噴水装置を置くと、噴水装置ごとにその中心の半径を実数Ri(0)にする効果がある.
入力
第1行mは、m組の試験データを示す各組の試験データの第1行には整数数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
問題を解く構想.
別のブログを参照してください.https://blog.csdn.net/wingrez/article/details/82012429
リファレンスコード

#include
#include
#include
#define MAXN 605
using namespace std;
double arr[MAXN];
bool cmp(double a,double b){
	return a>b;
}
int main(){
	int m;
	scanf("%d",&m);
	while(m--){
		int n;
		scanf("%d",&n);
		int i,j;
		for(i=0;i<n;i++)
			scanf("%lf",&arr[i]);
		sort(arr,arr+n,cmp);
		int ans=0;
		double len=0;
		for(i=0;i<n;i++){
			if(arr[i]>1){
				len=len+(sqrt(arr[i]*arr[i]-1))*2;
				ans++;
				if(len>=20) break;
			}
			else break;
		}
		printf("%d
",ans);
	}
	return 0;
}