首页 > ACM题库 > HDU-杭电 > hdu 2439 The Mussels-贪心-[解题报告]C++
2014
01-26

hdu 2439 The Mussels-贪心-[解题报告]C++

The Mussels

问题描述 :

"To be or not to be, that is the question." Now FJ( Frank&John) faces a serious problem.

FJ is breeding mussels these days. The mussels all want to be put into a culturist with a grade no little than their own grades. FJ accept their requirements.

FJ provides culturists of different grades, all having a certain capacity. FJ first put mussels into culturists with the same grade until they are full. Then he may put some mussels into some potential culturists that still have capacity.

Now, FJ wants to know how many mussels can be put into the culturists.

输入:

For each data set:
The first line contains two integers, n and m(0<n<=100000,0<m<=1000000), indicating the number of culturists and the number of mussels. The ith culturist has a grade i, and grade 1 is considered the highest.

The second line contains n integers indicating the culturists’ capacity in order.

The third line contains m integers all in the range 1~n, indicating the mussels’ grade in order.

Proceed to the end of file.

输出:

For each data set:
The first line contains two integers, n and m(0<n<=100000,0<m<=1000000), indicating the number of culturists and the number of mussels. The ith culturist has a grade i, and grade 1 is considered the highest.

The second line contains n integers indicating the culturists’ capacity in order.

The third line contains m integers all in the range 1~n, indicating the mussels’ grade in order.

Proceed to the end of file.

样例输入:

4 4
100 4 4 4
1 2 3 4
4 3
1 1 1 1
4 2 2

样例输出:

4
3

看到这个题,有容量,有匹配关系,第一反应就是网络流,但是看到数据比较大,加了点优化,把各个等级的mussel的数量统计一下,缩掉一部分顶点,抱着会TLE的心态提交,结果过了,不过跑了600多ms,最后一名了=。=

 

后来看别人的报告说排序加贪心就行了,想想对的,把等级高的mussel尽量往等级高的culturist里放就好,就像坐公交车的时候,那些先上车的人(等级高的mussel)有较多主动权,尽量往车后面走(等级高的culturist),这样公交车就能装更多人了

 

网络流代码:

#include<iostream>
#include<cstdio>
#include<memory.h>
#include<iostream>
using namespace std;
const int MAX=1100005;
const int inf=1<<30;
struct node
{
	int v,c,next;
}g[MAX+10000];
int adj[MAX],cur[MAX],dis[MAX],num[MAX],pre[MAX],grade[MAX];
int s,t,vn,e,n,m,cnt;
void add(int u,int v,int c)
{
	g[e].v=v; g[e].c=c; g[e].next=adj[u]; adj[u]=e++;
	g[e].v=u; g[e].c=0; g[e].next=adj[v]; adj[v]=e++;
}
int sap()  
{  
    int i,u,v,flow=0,aug=inf,flag;  
    for(i=0;i<=vn;i++)  
    {  
        dis[i]=num[i]=0;  
        cur[i]=adj[i];  
    }  
    num[0]=vn;  
    pre[s]=u=s;  
    while(dis[s]<vn)  
    {  
        flag=0;  
        for(i=cur[u];i!=-1;i=g[i].next)  
        {  
            v=g[i].v;  
            if(g[i].c&&dis[u]==dis[v]+1)  
            {  
                flag=1;  
                pre[v]=u;  
                cur[u]=i;  
                aug=aug<g[i].c?aug:g[i].c;  
                u=v;  
                if(u==t)  
                {  
                    flow+=aug;  
                    while(u!=s)  
                    {  
                        u=pre[u];  
                        g[cur[u]].c-=aug;  
                        g[cur[u]^1].c+=aug;  
                    }  
                    aug=inf;  
                }  
                break;  
            }  
        }  
        if(flag)  
            continue;  
        if(--num[dis[u]]==0)  
            break;  
        for(dis[u]=vn,i=adj[u];i!=-1;i=g[i].next)  
        {  
            v=g[i].v;  
            if(g[i].c&&dis[v]<dis[u])  
            {  
                dis[u]=dis[v];  
                cur[u]=i;  
            }  
        }  
        dis[u]++;  
        num[dis[u]]++;  
        u=pre[u];  
    }  
    return flow;  
}  
int main()
{
	int i,j,maxx=-1;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(adj,-1,sizeof(adj));
		memset(grade,0,sizeof(grade));
		e=cnt=0;
		t=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&j);
			add(i,t,j);
		}
		for(i=1;i<=m;i++)
		{
			scanf("%d",&j);
			if(j>maxx)
				maxx=j;
			if(!grade[j])
				cnt++;
			grade[j]++;
		}
		s=n+cnt+1;
		vn=s+1;
		for(i=1,cnt=0;i<=maxx;i++)
		{
			if(grade[i])
			{
				//cout<<grade[i]<<endl;
				cnt++;
				add(s,n+cnt,grade[i]);
				for(j=i;j>=1;j--)
					add(n+cnt,j,grade[i]);
			}
		}
		printf("%d/n",sap());
	}
	return 0;
}

解题转自:http://blog.csdn.net/scorpiocj/article/details/6227517


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.