向往的气球

向往的气球

时间: 1ms        内存:128M

描述:

一年一度的计控ACM院赛即将来临。除了ACMers以外,志愿者们也非常的忙碌。他们需要将各种颜色的气球分配给A掉相应题目的队伍。现在,所有比赛队伍的成员都处在一个房间中,这个房间是一个二维坐标系,大小为1000行x1000列。
每一个坐标对应着空座位或某个参赛队伍。每一分钟,志愿者们都应该把所有的气球聚集在一起。志愿者将会被告知把气球送到哪里。为了保证工作的效率,对于两个坐标(x1,y1)和(x2,y2),如果|x1-x2|不大于k 或者 |y1-y2|不大于k,则这两个坐标的气球由同一个志愿者配送。你能知道最少需要多少志愿者,才能配送完所有的气球吗?

输入:

第一行包含一个整数T,表示有T组数据。
对于每一组数组,这里将有n+1行
第一行:输入两个整数n,k; n表示气球的数量,k表示题目中的k值
接下来的n行中,每一行包含两个整数r,c。表示气球应该被送往r行,c列。请注意坐标可能会相同。
题目中保证:T<=100,1<=n<=10000,1<=k,r,c<=1000

输出:

对于每一组数据,你需要输出一行
输出最少需要的志愿者数量

示例输入:

2
3 5
1 1
10 6
15 20
2 5
1 1
7 7

示例输出:

1
2

提示:

参考答案(内存最优[1276]):

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e4+5;

int n,m,f[maxn];
struct node {
    int x,y,idx;
} a[maxn];

bool cmp1(node a,node b) { return a.x<b.x; }
bool cmp2(node a,node b) { return a.y<b.y; }
int Find(int x)
{
    if(f[x]==x)
        return x;
    else
    {
        f[x]=Find(f[x]);
        return f[x];
    }
   // return f[x]==x?x:f[x]=Find(f[x]);
 }
void Union(int x,int y) {
    x=Find(a[x].idx),
    y=Find(a[y].idx);
    if(x!=y)
        f[y]=x;
    }
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
       // memset(f,-1,sizeof f);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            f[i]=i;
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&a[i].x,&a[i].y);
            a[i].idx=i;
        }
        sort(a+1,a+n+1,cmp1);
        for(int i=1;i<n;i++)
            if(a[i+1].x-a[i].x<=m)
                Union(i+1,i);
        sort(a+1,a+1+n,cmp2);
        for(int i=1;i<n;i++)
            if(a[i+1].y-a[i].y<=m)
                Union(i+1,i);
        int ans = 0;
        for(int i=1;i<=n;i++)
            if(f[a[i].idx]==a[i].idx)
                ans++;
        printf("%d\n",ans);
    }
    return 0;
}

参考答案(时间最优[11]):

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e4+5;

int n,m,f[maxn];
struct node {
    int x,y,idx;
} a[maxn];

bool cmp1(node a,node b) { return a.x<b.x; }
bool cmp2(node a,node b) { return a.y<b.y; }
int Find(int x)
{
    if(f[x]==x)
        return x;
    else
    {
        f[x]=Find(f[x]);
        return f[x];
    }
   // return f[x]==x?x:f[x]=Find(f[x]);
 }
void Union(int x,int y) {
    x=Find(a[x].idx),
    y=Find(a[y].idx);
    if(x!=y)
        f[y]=x;
    }
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
       // memset(f,-1,sizeof f);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            f[i]=i;
        for(int i=1;i<=n;i++) {
            scanf("%d%d",&a[i].x,&a[i].y);
            a[i].idx=i;
        }
        sort(a+1,a+n+1,cmp1);
        for(int i=1;i<n;i++)
            if(a[i+1].x-a[i].x<=m)
                Union(i+1,i);
        sort(a+1,a+1+n,cmp2);
        for(int i=1;i<n;i++)
            if(a[i+1].y-a[i].y<=m)
                Union(i+1,i);
        int ans = 0;
        for(int i=1;i<=n;i++)
            if(f[a[i].idx]==a[i].idx)
                ans++;
        printf("%d\n",ans);
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注