2026牛客寒假算法基础集训营6 A

小L的三角尺

https://ac.nowcoder.com/acm/contest/120566/A

大致思路:

首先记录所有斜边的总长度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);
}

如有错误烦请指正谢谢

全部评论

相关推荐

01-14 16:23
广州商学院 Java
双非后端失败第N人:如果准备好了可以直接投字节,字节是最不看学历的,只要想面,大概率都能给你约面。
双非有机会进大厂吗
点赞 评论 收藏
分享
评论
5
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务