ZOJ-3597-Hit the Target!(线段树+扫描线)

题解引自:http://www.cnblogs.com/wuyiqi/archive/2012/04/28/2474614.html

这题和着题解一块看,看了半天才看懂的....菜菜....

题意：有一排的枪编号依次为1~n 有一排靶子编号依次为1~m

告诉你哪些枪能打中哪些靶子，然后如果每次只能选连续的P把枪，连续的Q个靶子，每次能打中的靶子的最大值为多少

答案是把每次打中的最大值相加再除以总的次数

即选择 1~P 的枪能打中的最多的靶子的数量 + 2~p+1 的枪能打中的最多的靶子的数量 +。。。n-p+1~n的枪能打中的最多的靶子的数量 /（n-p+1）

注意，每把枪最多只能打一个靶子

解法：将题目中的关系转换为坐标 以枪为纵坐标 a 能打中 b ，在坐标系中为（b，a），然后连续的P把枪和连续的Q个靶子则可以表示为

用一个P x Q的矩形去覆盖，最多能覆盖的总的点数，就是poj 2482 了，但要注意一点，如果两根同一高度的水平线的距离小于Q，则重叠的部分职能算一次，因为每把枪只能打一个靶子

// File Name: 3597.cpp

// Author: Zlbing

// Created Time: 2013/7/21 14:25:06

#include<iostream>

#include<string>

#include<algorithm>

#include<cstdlib>

#include<cstdio>

#include<set>

#include<map>

#include<vector>

#include<cstring>

#include<stack>

#include<cmath>

#include<queue>

using namespace std;

#define CL(x,v); memset(x,v,sizeof(x));

#define INF 0x3f3f3f3f

#define LL long long

#define REP(i,r,n) for(int i=r;i<=n;i++)

#define RREP(i,n,r) for(int i=n;i>=r;i--)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

const int MAXN=5e4+;

struct point{

    int x,y;

    bool operator <(const point& rsh)const{

        if(y==rsh.y)return x<rsh.x;

        else return y<rsh.y;

    }

}G[];

int sum[MAXN<<];

int col[MAXN<<];

void pushup(int rt)

{

    sum[rt]=max(sum[rt<<],sum[rt<<|]);

}

void pushdown(int rt)

{

    if(col[rt])

    {

        sum[rt<<]+=col[rt];

        sum[rt<<|]+=col[rt];

        col[rt<<]+=col[rt];

        col[rt<<|]+=col[rt];

        col[rt]=;

    }

}

void update(int L,int R,int flag,int l,int r,int rt)

{

    if(L<=l&&R>=r)

    {

        col[rt]+=flag;

        sum[rt]+=flag;

        return;

    }

    pushdown(rt);

    int m=(l+r)>>;

    if(L<=m)update(L,R,flag,lson);

    if(R>m)update(L,R,flag,rson);

    pushup(rt);

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,m,p,q,K;

        scanf("%d%d%d%d",&n,&m,&p,&q);

        scanf("%d",&K);

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

        {

            scanf("%d%d",&G[i].y,&G[i].x);

        }

        sort(G,G+K);

        int ans=;

        int j=,k=;

        CL(sum,);

        CL(col,);

        for(int i=;i+p-<=n;i++)

        {

            for(;G[j].y-i<p&&j<K;j++)

            {

                if(j+<K&&G[j].y==G[j+].y&&G[j+].x-G[j].x<q)

                    update(G[j].x,G[j+].x-,,,m,);

                else

                    update(G[j].x,min(m,G[j].x+q-),,,m,);

            }

            ans+=sum[];

            for(;k<j&&G[k].y==i;k++)

            {

                if(k+<j&&G[k].y==G[k+].y&&G[k+].x-G[k].x<q)

                    update(G[k].x,G[k+].x-,-,,m,);

                else

                    update(G[k].x,min(m,G[k].x+q-),-,,m,);

            }

        }

        printf("%.2lf\n",(double)ans/(n-p+));

    }

    return ;

}