题解 | #A

题目

输入

输出

思路

要使斜边和最小，就等价于每一次的额度使用后，创造出来的斜边最小，也就是斜边的变化率最大。

可以先算出所有的斜边的总和，已经斜边的变化率，然后将变化率放入优先队列里从大到小排列。

找出最大的变化率，并在ans上减去，同时更新此时三角形的变化率，放入优先队列。

最后保留六位小数输出答案。

完整代码

```#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[500005];
ll b[500005];
double ans;
signed main(){
    int n,w;
    cin>>n>>w;
    priority_queue<pair<double, int>> pq;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i] >> b[i];
        ans += sqrt(a[i] * a[i] + b[i] * b[i]);
        pq.push({sqrt(a[i] * a[i] + b[i] * b[i]) - sqrt(a[i] * a[i] + (b[i] - 1) * (b[i] - 1)), i});
    }
     while (w) {
        double temp = pq.top().first;
        int i = pq.top().second;
        pq.pop();
        w--;
        ans -= temp;
        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});
    }
     cout << fixed << setprecision(15) << ans;
    return 0;
}