首页 > 搜索 > BFS搜索 > HDU 3399-Roba’s dream-贪心-[解题报告]HOJ
2014
03-23

HDU 3399-Roba’s dream-贪心-[解题报告]HOJ

Roba’s dream

问题描述 :

LCY has made comments to HDU-ACM team leaders, “some team leaders can change girl ACMers into their girl friends, it’s a great job; but menjitianya2007 can make his girl friend be an ACM partner, it’s great beyond .”(http://blog.sina.com.cn/s/blog_5dc12a880100c6n1.html) Yes , it is true that there are many lovers in ACM teams, boy ACMers’ nuttiness and patience attract PLMMs. How to catch the girls’ heart? So as to realize roba’s third dream(http://roba.ycool.com/post.1738620.html) , lxhgww decides to invite the lovers in all ACM teams and let them talk something about their love experience.

lxhgww decide to choose at most one of each couple to talk about their experience. He thought people in different height have different love experience, so he would like to invite ACMers with different height to give a talk, what’s more, the shortest one (and also the first one) invited should always be 1.500000m and the (i+1)th ACMer should be exactly taller than the ith one by 0.000001m. Now,lxhgww want to the maximal number of ACMers he can invite. If he invited ACMers whose heights are1.500000,1.500001,but he can’t invite a 1.500002m tall,then 2 will be the maximal number.

输入:

The first line is the case number T(<=15).
For each case, there is an integer N(<=1000000) in the first line indicating N couples of lovers.
The next N lines of each case have two numbers round to 6 decimals each, they are the height of the ith couple of ACMers, all are no shorter than 1.5m.,and no higher than 2.0m.

输出:

The first line is the case number T(<=15).
For each case, there is an integer N(<=1000000) in the first line indicating N couples of lovers.
The next N lines of each case have two numbers round to 6 decimals each, they are the height of the ith couple of ACMers, all are no shorter than 1.5m.,and no higher than 2.0m.

样例输入:

1
3
1.500000 1.500001
1.500002 1.500001
1.500003 1.500004

样例输出:

2

本来想用匹配水过去的 结果水不过去 只好看题解了

每个连通分支 如果是图,就必然能分配到 是树就贪心 这个建图思路相当精妙啊

注意坐标枚举要到500001,不然会wa

#include <iostream>
using namespace std;
const int maxn=1100000,maxm=4*maxn;
struct Edge
{
int y;
int ne;
} e[maxm];
int st[maxn],ee;
void addedge(int x,int y)
{
e[ee].y=y;e[ee].ne=st[x];st[x]=ee++;
e[ee].y=x;e[ee].ne=st[y];st[y]=ee++;
}
int c[maxn];
int numn[maxn],numm[maxn],lost[maxn];
int s[maxn],head,tail;
void bfs(int k,int col)
{
int i;
head=0;tail=1;s[0]=k;
c[k]=col;
while (head<tail)
{
   k=s[head++];
   for (i=st[k];i!=-1;i=e[i].ne)
   {
    numm[col]++;
    if (c[e[i].y]==0)
    {
     c[e[i].y]=col;
     s[tail++]=e[i].y;
    }
   }
}
numn[col]=tail;
}
int main()
{
freopen("in.in","r",stdin);
int cass;
for (scanf("%d",&cass);cass–;)
{
   int n;
   scanf("%d",&n);
   int i,x,y,z1,z2;
   memset(st,-1,sizeof(st));
   ee=0;
   for (i=0;i<n;i++)
   {
    scanf("%d.%d %d.%d",&z1,&x,&z2,&y);
    x=z1*1000000+x-1500000;
    y=z2*1000000+y-1500000;
    addedge(x,y);
   }
   memset(c,0,sizeof(c));
   memset(numn,0,sizeof(numn));
   memset(numm,0,sizeof(numm));
   memset(lost,-1,sizeof(lost));
   int col=0;
   for (i=0;i<maxn;i++) if (c[i]==0)
   {
    col++;
    bfs(i,col);
   }
   for (i=1;i<=col;i++) numm[i]/=2;
   for (i=0;i<maxn;i++) if (numn[c[i]]>numm[c[i]]) if (lost[c[i]]<i) lost[c[i]]=i;
   for (i=0;i<maxn;i++)
    if (lost[c[i]]==i) break;
   printf("%d\n",i);
}
return 0;
}

参考:http://hi.baidu.com/lccycc_acm/item/bba7fb742e36ce5d0d0a07a5


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮