这两份代码区别在哪里?
查看原帖
这两份代码区别在哪里?
322285
北京楼主2021/8/11 11:43

未AC:

//P6033 [NOIP2004 提高组] 合并果子 加强版
#include<cstdio>
#include<queue>

#define int unsigned long long

std::queue<int>q1;
std::queue<int>q2;

const int N=1e5+10;

int buc[N],ans;

inline int read()
{
	int s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
	return s;
}


signed main()
{
	int n=read();
	for(int i=1;i<=n;++i)
		buc[read()]++;
	
	for(int i=1;i<=N;++i)
		if(buc[i])
			for(int j=1;j<=buc[i];++j)
				q1.push(i);
	while(!q1.empty())
	{
		int u=0,v=0;
		if(!q2.empty()&&q2.front()<q1.front())
			{u=q2.front();q2.pop();}
		if(!q2.empty()&&q2.front()<q1.front())
			{v=q2.front();q2.pop();}
		if(!u&&!q1.empty()){u=q1.front();q1.pop();}
		else if(!u){u=q2.front();q2.pop();}
		if(!v&&!q1.empty()){v=q1.front();q1.pop();}
		else if(!v){v=q2.front();q2.pop();}
		//printf("%llu %llu\n",u,v);
		q2.push(u+v);
		ans+=u+v;
	}
	while(q2.size()>1)
	{
		int u=q2.front();q2.pop();
		int v=q2.front();q2.pop();
		q2.push(u+v);
		ans+=u+v;
	}
	
	printf("%llu",ans);
}

对着示范代码改一改取两个最小的果子堆的代码就AC了:

//P6033 [NOIP2004 提高组] 合并果子 加强版
#include<cstdio>
#include<queue>

#define int unsigned long long

std::queue<int>q1;
std::queue<int>q2;

const int N=1e5+10;

int buc[N],ans;

inline int read()
{
	int s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
	return s;
}


signed main()
{
	int n=read();
	for(int i=1;i<=n;++i)
		buc[read()]++;
	
	for(int i=1;i<=N;++i)
		if(buc[i])
			for(int j=1;j<=buc[i];++j)
				q1.push(i);
	while(!q1.empty())
	{
		int u=0,v=0;
		if(q2.empty()||(!q1.empty()&&q1.front()<q2.front())){u=q1.front();q1.pop();}
		else {u=q2.front();q2.pop();}
		if(q2.empty()||(!q1.empty()&&q1.front()<q2.front())){v=q1.front();q1.pop();}
		else {v=q2.front();q2.pop();}
		//printf("%llu %llu\n",u,v);
		q2.push(u+v);
		ans+=u+v;
	}
	while(q2.size()>1)
	{
		int u=q2.front();q2.pop();
		int v=q2.front();q2.pop();
		q2.push(u+v);
		ans+=u+v;
	}
	
	printf("%llu",ans);
}

感觉好像效果都一样?为什么一份可以AC一份不可以?

感谢大佬指教!

2021/8/11 11:43
加载中...