POJ 1328&&2109&&2586

　　这次是贪心（水笔贪心）专题。

　　先看1328，一道经典的导弹拦截（或者是打击？不懂背景）。

　　大意是说在一个坐标系中有一些点（或是导弹），你要在x轴上建一些东西，它们可以拦截半径为d的圆范围中的点。问最少修建的个数，不可能输出-1。

　　经典问题了哈，主要是把二维的转成一维。

　　对于每个要拦截的点以d为半径画一个圆。会与x轴有0/1/2个交点。如果没有交点直接退出-1即可，一个交点也可以看成两个交点重合。

　　这样我们就得到了一些线段，然后就是区间覆盖了。贪心走一遍即可。

　　两个端点的坐标勾股定理就好了：x±sqrt(d^2-y^2)

　　注意检查你的输出，我因为把Case 打成了case WA了N次（......）。

　　CODE

#include<cstdio>

#include<math.h>

#include<algorithm>

using namespace std;

const int N=;

struct data

{

    double x,y;

}a[N];

int n,d,i,kinds,x,y;

inline void read(int &x)

{

    x=; char ch=getchar(); int flag=;

    while (ch<''||ch>'') { if (ch=='-') flag=-; ch=getchar(); }

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    x*=flag;

}

inline int comp(data a,data b)

{

    return a.x<b.x;

}

int main()

{

    for (kinds=;;++kinds)

    {

        read(n); read(d);

        if (!n&&!d) break;

        bool flag=;

        for (i=;i<=n;++i)

        {

            read(x); read(y);

            if (y>d) flag=;

            a[i].x=x-sqrt(1.0*d*d-1.0*y*y); a[i].y=x+sqrt(1.0*d*d-1.0*y*y);

        }

        if (flag) { printf("Case %d: -1\n",kinds); continue; }

        sort(a+,a+n+,comp);

        int ans=;

        double last=a[].y;

        for (i=;i<=n;++i)

        if (a[i].x>last) ++ans,last=a[i].y; else if (a[i].y<last) last=a[i].y;

        printf("Case %d: %d\n",kinds,ans);

    }

    return ;

}

　　2109：这是个智障题。

　　有一个等式k^n=p，现在给出n，p，让你求出k

　　这不是直接把p开n次方即可的事情吗？和贪心有何瓜葛？

　　double的精度在这题应该不会炸，开方也不用手写或高精检验，在精度范围内（k在1~1e9之间），所以用pow来做分数次幂就行了。

　　CODE

#include<cstdio>

#include<cmath>

using namespace std;

double n,p;

int main()

{

    while (scanf("%lf%lf",&n,&p)!=EOF) printf("%.0lf\n",pow(p,/n));

    return ;

}

　　2586：一个很简单的贪心题。

　　题目大意是一个二货公司每个月要么盈利s元，要么亏损d元，但是他们在一年中任意连续的5个月（1~5,2~6……）的盈亏和必须是负的。问你一年中可能盈利吗,可以就输出最大盈利值。

　　想一下就知道亏损的月份放在最后面最好（可以被多次利用）

　　所以假定他们12个月都盈利，在进行检查，如果和大于0就从后面开始修改。

　　CODE

#include<cstdio>

#include<cstring>

using namespace std;

int sum,s,d,i;

bool f[];

inline void check(int a,int b)

{

    for(;;)

    {

        int res=;

        for (int i=a;i<=b;++i)

        if (f[i]) res+=s; else res-=d;

        if (res>=)

        {

            int i=b;

            while (!f[i]&&i>a) --i;

            f[i]=;

        } else break;

    }

}

int main()

{

    while (scanf("%d%d",&s,&d)!=EOF)

    {

        memset(f,true,sizeof(f));

        sum=;

        for (i=;i<=;++i)

        check(i,i+);

        for (i=;i<=;++i)

        if (f[i]) sum+=s; else sum-=d;

        if (sum<) puts("Deficit"); else printf("%d\n",sum);

    }

    return ;

}

巴特西

POJ 1328&&2109&&2586

最新文章

热门文章