A.小L的三角尺

题意: 现有n把三角尺，我们得知第i个三角尺的直角边是，我们可以对任意三角尺的减去一个数，但不能是大于的数，且所有减去的长度总和不能大于w，使得最终所有三角尺的斜边长度总和最小。

知识点: 贪心，优先队列

思路: 我们可以把题意分解为一个一个减，通过优先队列来维护-1原先长度-现在长度的最大值，每减一次就更新一次。具体做法叙述如下:

创建一个倒序排序的三元组优先队列，依次按输入算出

并将其推入队列push({d,x,y});（因为数据范围规定输入的y>=1，所以不用担心直接减成负数的情况。）

接着进入循环，循环条件为队列非空以及i<w。

循环内取出栈顶元素的x和y，然后将元素出队并判断y是大于0，若不大于则直接算出斜边加入到ans，若大于则y-1并算出新的d并入栈。

循环结束则取出所有栈内元素算出斜边长度加到ans里面得出最终答案。

参考代码:

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define PLL pair<ll,ll>
#define PII pair<int,int>
#define endl '\n'
using namespace std;
int main()
{
	cin.tie(0),cout.tie(0),ios::sync_with_stdio(0);
	int n,w;
	double ans=0;
	cin >> n >> w;
	priority_queue<pair<double,PLL>,vector<pair<double,PLL>>> pq;
	for(int i=0;i<n;i++){
		ll x,y;
		cin >> x >> y;
		double d=sqrt(x*x+y*y)-sqrt(x*x+(y-1)*(y-1));
		pq.push({d,{x,y}});
	}
	for(int i=0;i<w&&!pq.empty();){
		PLL t=pq.top().second;
		pq.pop();
		if(t.second==0){
			ans+=sqrt(t.first*t.first+t.second*t.second);
			continue;
		}
        t.second--;	
		double d=sqrt(t.first*t.first+t.second*t.second)-sqrt(t.first*t.first+(t.second-1)*(t.second-1));
		pq.push({d,t});
        i++;
	}
	while(!pq.empty()){
		PLL t=pq.top().second;
		pq.pop();
		ans+=sqrt(t.first*t.first+t.second*t.second);
	}
	cout << fixed << setprecision(15) << ans;
	return 0;
}