NYOJ 12噴水装置(二)
1519 ワード
タイトルリンク:http://acm.nyist.net/JudgeOnline/problem.php?pid=12
問題を解く難点と考え方:
1.欲張りと何の関係があるのかわからず、radar(nyoj 287)の問題に連絡してみると、似ている点がわかり、すぐに区間カバーの問題を思い浮かべますが、このカバーは少し違います
2.区間カバーであることが分かったが、どのようにすべての場所をカバーするか分からない(最良の区間を選択して区間と区間の間に隙間がなく、線分の最末端まで).
3.貪欲な策略は左の端点を小さいから大きいまで並べ替えて、右の端点を選んで、右の端点ができるだけ覆うのが最も遠いようにします
コードは次のとおりです.
問題を解く難点と考え方:
1.欲張りと何の関係があるのかわからず、radar(nyoj 287)の問題に連絡してみると、似ている点がわかり、すぐに区間カバーの問題を思い浮かべますが、このカバーは少し違います
2.区間カバーであることが分かったが、どのようにすべての場所をカバーするか分からない(最良の区間を選択して区間と区間の間に隙間がなく、線分の最末端まで).
3.貪欲な策略は左の端点を小さいから大きいまで並べ替えて、右の端点を選んで、右の端点ができるだけ覆うのが最も遠いようにします
コードは次のとおりです.
#include
#include
#include
using namespace std;
const int MAX=10001;
struct interval{
double left,right;
};
bool order_by_right(struct interval a,struct interval b){
return a.left0)
{
a[i].left=temp_x-temp_w; //
a[i].right=temp_x+temp_w;
}
}
sort(a,a+pump_num,order_by_right);
double Max=0; // ( ) , ,Max ( , ( ))
double sum=0; //
while(sumMax) // , ( )
{
Max=a[i].right-sum;
}
}
if(Max==0) //while Max 0, ,
{
biaoji=0;
break;
}
else
{
count++;
sum+=Max; //
}
}
if(biaoji)
printf("%d
",count);
else
printf("0
");
}
return 0;
}