D - Maximizing Advertising

题目链接：https://cn.vjudge.net/contest/250168#problem/D

题目大意：给你一些点的坐标，这些点属于两个帮派，让你将这些点分进两个不能重叠的矩形中，问你最多两个矩形中不同帮派之和为多少？

具体思路：

将点分别按照x升序进行排序，按照y升序进行排序。横着扫描一遍，竖着扫描一遍，求出在扫描的过程中和的最大值。

AC代码;

#include<bits/stdc++.h>

using namespace std;

# define maxn 1000000+10

struct node

{

    int x,y;

    char cost;

} q[maxn];

bool cmp1(node t1,node t2)

{

    return t1.x<t2.x;

}

bool cmp2(node t1,node t2)

{

    return t1.y<t2.y;

}

int xb[maxn],xw[maxn],yb[maxn],yw[maxn];

void init()

{

    memset(xb,0,sizeof(xb));

    memset(xw,0,sizeof(xw));

    memset(yb,0,sizeof(yb));

    memset(yw,0,sizeof(yw));

}

int main()

{

    int n;

    scanf("%d",&n);

    getchar();

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

    {

        scanf("%d %d %c",&q[i].x,&q[i].y,&q[i].cost);

    }

    sort(q+1,q+n+1,cmp1);

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

    {

        if(q[i].cost=='b')

        {

            xb[i]++;

        }

        if(q[i].cost=='w')

        {

            xw[i]++;

        }

        xb[i]+=xb[i-1];

        xw[i]+=xw[i-1];//求x的前缀和

    }

    sort(q+1,q+n+1,cmp2);

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

    {

        if(q[i].cost=='b')

        {

            yb[i]++;

        }

        if(q[i].cost=='w')

        {

            yw[i]++;

        }

        yb[i]+=yb[i-1];

        yw[i]+=yw[i-1];//求y的前缀和

    }

    int maxx=-1;

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

    {

        int temp1=xb[i]+xw[n]-xw[i];

        int temp2=xw[i]+xb[n]-xb[i];

        maxx=max(maxx,max(temp1,temp2));

    }

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

    {

        int temp1=yb[i]+yw[n]-yw[i];

        int temp2=yw[i]+yb[n]-yb[i];

        maxx=max(maxx,max(temp1,temp2));

    }

    printf("%d\n",maxx);

    return 0;

}

巴特西

D - Maximizing Advertising

最新文章

热门文章