NYOJ 12噴水装置(二)

1519 ワード

タイトルリンク:http://acm.nyist.net/JudgeOnline/problem.php?pid=12
問題を解く難点と考え方:
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; }