大致思路:
首先记录所有斜边的总长度sum,优先队列记录每把三角尺直角边减少一斜边减少的值(直角边为0则不记录),下面统称收益,while循环循环w次,每次sum减去当前收益最大的三角尺,更新优先队列(当前边再减去一的收益),同样如果直角边减到0不再加入队列,最后输出sum即可。
代码如下:
void solve()
{
ll n,w;
double sum=0;
cin>>n>>w;
vector<ll>a(n),b(n),nw(n);
priority_queue<pair<double,ll>>pq;
for(ll i=0;i<n;i++)
{
cin>>a[i]>>b[i];
nw[i]=b[i];
sum+=sqrt(a[i]*a[i]+b[i]*b[i]);
if(b[i]>0)
pq.push({sqrt(a[i]*a[i]+b[i]*b[i])-sqrt(a[i]*a[i]+(b[i]-1)*(b[i]-1)),i});
}
ll i=0;
while(!pq.empty()&&i<w)
{
i++;
auto [sy,s]=pq.top();
pq.pop();
sum-=sy;
nw[s]--;
if(nw[s]>0)
pq.push({sqrt(a[s]*a[s]+nw[s]*nw[s])-sqrt(a[s]*a[s]+(nw[s]-1)*(nw[s]-1)),s});
}
printf("%.10f",sum);
}
如有错误烦请指正谢谢

京公网安备 11010502036488号