标签：cnt cmpt long t1 100005 摊位 ans 分配
- 你的做法模拟到了所有社团都至少分到了1个格子,用double实现会有精度问题,既然可以避免就避免吧
- 题解则观察到了分界值和划分出的席位数之间良好的单调关系,采用二分的方法求解
- 但这种做法有严重的精度问题,根源在于分界值趋近于0,可以通过取log或者拆分整数和小数的方法优化
点击查看代码
#include <bits/stdc++.h>
using namespace std;
long long w[100005],cnt[100005];
long long ans[100005],u[100005];
struct t1
{
long long cnt,w;
long long i;
bool pd;
};
auto cmpt=[](t1 a,t1 b)
{
if(a.w*(1<<b.cnt)!=b.w*(1<<a.cnt))
{
return a.w*(1<<b.cnt)<b.w*(1<<a.cnt);
}
if(a.pd^b.pd)
{
return b.pd==true;
}
if(a.w!=b.w)
{
return a.w<b.w;
}
return a.i>b.i;
};
priority_queue<t1,vector<t1>,decltype(cmpt)>q(cmpt);
bool cmp(long long a,long long b)
{
if(w[a]*(1<<cnt[b])!=w[b]*(1<<cnt[a]))
{
return w[a]*(1<<cnt[b])>w[b]*(1<<cnt[a]);
}
if(w[a]!=w[b])
{
return w[a]>w[b];
}
return a<b;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
long long n,h;
cin>>n>>h;
for(long long i=1;i<=n;i++)
{
cin>>w[i];
q.push((t1){0,w[i],i,true});
u[i]=i;
}
long long sum=0;
while(sum!=n&&h!=0)
{
t1 n1=q.top();
q.pop();
long long i=n1.i;
ans[i]++;
cnt[i]++;
h--;
sum+=(ans[i]==1);
q.push((t1){cnt[i],w[i],i,false});
}
if(h>0)
{
for(long long i=1;i<=n;i++)
{
ans[i]+=(h/n);
}
h%=n;
sort(u+1,u+n+1,cmp);
for(long long i=1;i<=h;i++)
{
ans[u[i]]++;
}
}
for(long long i=1;i<=n;i++)
{
cout<<ans[i]<<" ";
}
cout<<endl;
return 0;
}
标签：cnt,
cmpt,
long,
t1,
100005,
摊位,
ans,
分配
From： https://www.cnblogs.com/watersail/p/18680477