未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一份不可以?
感谢大佬指教!