acm------我的总结与思考

我在本周继续对贪心算法进行研究，做了不少题，但是我还是没有把acm和必修课课程学习平衡好，对acm的投入还是不够，打代码不熟练，思路不清晰，自学时效率很低，看别人的题解总是看半天也看不懂。我总结：我最大的问题，就是基本代码实现思路不清晰和办法不多。

以贪心算法为例，代码核心是排序，但是在输出时的细节处理如果处理不好也写不出程序。贪心是技术也是思想。但更多的是思想。学会了贪心不一定能写出优秀的代码，但是用贪心效率肯定高很多。这就是前期刷水题的重要性啊。计数是个好办法，取0是个好办法。

总结贪心的题型：
货币选择问题
区间调度问题
字典序最小问题
多机调度问题
小船过河问题
区间覆盖问题

我不是很会的题：
区间覆盖问题
POJ1328是一道经典的贪心算法例题。题目大意是假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上，只能覆盖d距离，所以如果小岛能够被覆盖到的话，它们之间的距离最多为d。题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目。对于每个小岛，我们可以计算出一个雷达所在位置的区间。

问题转化为如何用尽可能少的点覆盖这些区间。先将所有区间按照左端点大小排序，初始时需要一个点。如果两个区间相交而不重合，我们什么都不需要做；如果一个区间完全包含于另外一个区间，我们需要更新区间的右端点；如果两个区间不相交，我们需要增加点并更新右端点。
acm------我的总结与思考

#include<cmath>  
#include<iostream>  
#include<algorithm>  
using namespace std;  
struct Point  
{  
    double x;  
    double y;  
}point[1000];  
  
int cmp(const void *a, const void *b)  
{  
    return (*(Point *)a).x>(*(Point *)b).x?1:-1;  
}  
  
int main()  
{  
    int n,d;  
    int num=1;  
    while(cin>>n>>d)  
    {  
        int counting=1;  
        if(n==0&&d==0) break;  
        for(int i=0;i<n;i++)  
        {  
            int x,y;  
            cin>>x>>y;  
            if(y>d)  
            {  
                counting=-1;  
            }  
            double t=sqrt(d*d-y*y);  
            //转化为最少区间的问题   
            point[i].x=x-t;  
            //区间左端点   
            point[i].y=x+t;  
            //区间右端点   
        }  
        if(counting!=-1)  
        {  
            qsort(point,n,sizeof(point[0]),cmp);  
            //按区间左端点排序   
            double s=point[0].y;  
            //区间右端点   
            for(int i=1;i<n;i++)  
            {  
                if(point[i].x>s)  
                //如果两个区间没有重合,增加雷达数目并更新右端点   
                {  
                    counting++;  
                    s=point[i].y;   
                }  
                else if(point[i].y<s)  
                //如果第二个区间被完全包含于第一个区间,更新右端点   
                {  
                    s=point[i].y;  
                }  
            }  
        }  
        cout<<"Case "<<num<<':'<<' '<<counting<<endl;  
        num++;   
    }  
}

要学的还有很多，坚持下去。

acm------我的总结与思考

相关推荐