SDNU1235(及及debug之初出茅庐)(pair的应用)

1.首先这道题的数据很大，所给的p和q达到了10^10;超出了int型的最高范围（量级是10^9），因此建议将程序中和坐标相关的所有变量都设置为long long 型

2.关于本题的思考方向：首先，这道题不可能使用遍历来做，时间和空间都是不允许的，（n最高为10^10）

其次，我们通过思考发现： 这道题目是以bug为中心展开的。所以我们的思考就以bug为中心。

3.输入数据是

（1）矩阵的大小（注意xi<p,yi<q），这种输入的是矩阵范围的数据一定要注意边界的限制，有时候WA的原因可能就在此处。

（2）bug的坐标和数量

4.首先我们可以用结构体来存放bug的坐标，用结构体来存放提示的坐标和数量

其次，我们用sort排序的方法控制bug的输出顺序

重点是：处理提示的重合问题：使用两次sort排序进行重合提示的消除操作

5.本题中最重要的一件事是pair的应用：虽然我们可以使用两层for循环来控制有bug的提示处的输出，但是使用pair不仅简洁而且方便，最重要的是减少了时间复杂度。所以，有必要来介绍一下pair。

（1）pair被包含在一个头文件中，<utility>,使用时需要引入。

（2）pair的实现是一个结构体，因此可以直接用first和second引用其成员变量。

（3）pair是将两个数据组合成为一个数据来使用，它使得两个数据能够成为一个组合的整体（和结构体类似）。

（4）pair中的两个数据可以是不同的数据类型。

（5）pair和map<>联合使用可以判定成为一个坐标整体的标记。

6.结论的推广：利用pair<A,B>p和map<p,bool>m不仅仅可以标记横纵坐标，而且可以推广到任意两种数据组成的整体。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<utility>//定义了pair
#include<map>
#include<vector>
using namespace std;
const int maxn=1005;//以bug为中心遍历
typedef pair<long long,long long>location;
map<location,bool>exist;//存在返回1
struct node
{long long x;long long y;
} link[maxn];
struct st
{long long x;long long y;int num;
} pp[10*maxn];
bool cmp1(node a,node b)
{if(a.x<b.x)return true;else if(a.x==b.x&&a.y<b.y)return true;elsereturn false;
}
bool cmp2(st a,st b)
{if(a.num>b.num)return true;else if(a.num==b.num&&a.x<b.x)return true;else if(a.num==b.num&&a.x==b.x&&a.y<b.y)return true;elsereturn false;
}
long long n,p,q,a,b,nums;
void init()
{memset(link,0,sizeof(link));memset(pp,0,sizeof(pp));nums=0;exist.clear();
}
int dir[8][2]= {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
int main()
{int cases=1;while(~scanf("%d",&n)){init();scanf("%lld%lld",&p,&q);for(int i=0; i<n; i++){scanf("%lld%lld",&a,&b);link[i].x=a;link[i].y=b;exist[location(a,b)]=true;}sort(link,link+n,cmp1);for(int i=0; i<n; i++){for(int j=0; j<8; j++){long long xx=link[i].x+dir[j][0];long long yy=link[i].y+dir[j][1];if(xx>=0&&xx<p&&yy>=0&&yy<q){pp[nums].x=xx;pp[nums].y=yy;pp[nums].num++;nums++;}}}sort(pp,pp+nums,cmp2);printf("Case #%d:\n",cases++);for(int i=0; i<nums; i++)if(pp[i].x==pp[i-1].x&&pp[i].y==pp[i-1].y){pp[i].num+=pp[i-1].num;pp[i-1].num=0;}sort(pp,pp+nums,cmp2);for(int i=0; i<nums; i++){if(exist[location(pp[i].x,pp[i].y)]==true);else if(pp[i].num>0)printf("%lld %lld %d\n",pp[i].x,pp[i].y,pp[i].num);}for(int i=0; i<n; i++)printf("%lld %lld\n",link[i].x,link[i].y);printf("\n");}return 0;
}