• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

m皇后

开发技术 开发技术 6小时前 4次浏览

题目:https://ac.nowcoder.com/acm/problem/15295

思路:

结构体的id用来记录这个点,不然排序会把点的顺序打乱

排四个序,分别代表上下,左右,正对角线,副对角线

注意排序时遇到相等的,要根据其他坐标来排,例如x相同时,y最小的威胁只有右边,y最大的威胁只有左边,两人端点时只加了一次的

每排一遍序就要扫一遍

例如q[ i ].x==q[i-1].x

cnt[ q[ i ].id ]++;   是指这个点左边有威胁

cnt[ q[ i-1 ].id ]++;   是指这个点右边有威胁

最后从1-m遍历一次,统计次数

//换位思考从各个方向来遍历//当一个方向行不通,学会逆向思考
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=1e5+7;
int n,m;
int cnt[maxn]={0};
int num[10]={0};
struct qi
{
    int x,y,id;
};
struct qi q[maxn];
int cmp1(qi a,qi b)
{  if(a.x==b.x)
return a.y<b.y;
    return a.x<b.x;
}
int cmp2(qi a,qi b)
{  if(a.y==b.y)
return a.x<b.x;
    return a.y<b.y;
}
int cmp3(qi a,qi b)
{  if(a.x-a.y==b.x-b.y)
 return a.x<b.x;

    return a.x-a.y<b.x-b.y;
}
int cmp4(qi a,qi b)
{if(a.x+a.y==b.x+b.y)
 return a.x<b.x;
    return a.x+a.y<b.x+b.y;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&q[i].x,&q[i].y);
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp1);
    for(int i=2;i<=m;i++)
    {
        if(q[i].x==q[i-1].x)
        {
            cnt[q[i].id]++;
            cnt[q[i-1].id]++;
        }
    }

        sort(q+1,q+m+1,cmp2);
  for(int i=2;i<=m;i++)
    {
        if(q[i].y==q[i-1].y)
        {
            cnt[q[i].id]++;
            cnt[q[i-1].id]++;
        }
    }
            sort(q+1,q+m+1,cmp3);
for(int i=2;i<=m;i++)
    {
        if(q[i].x-q[i].y==q[i-1].x-q[i-1].y)
        {
            cnt[q[i].id]++;
            cnt[q[i-1].id]++;
        }
    }
                sort(q+1,q+m+1,cmp4);
for(int i=2;i<=m;i++)
    {
        if(q[i].x+q[i].y==q[i-1].x+q[i-1].y)
        {
            cnt[q[i].id]++;
            cnt[q[i-1].id]++;
        }
    }
    for(int i=1;i<=m;i++)
    {
        num[cnt[q[i].id]]++;
    }
    for(int i=0;i<8;i++)
        printf("%d ",num[i]);
    printf("%dn",num[8]);
}

 


程序员灯塔
转载请注明原文链接:m皇后
喜欢 (0)