寒假算法基础集训营6 A题题解

对于每把尺子，打磨的边际收益（斜边长度减少量）是递减的。由于w不大，使用贪心策略即可，每次选择当前边际收益最大的尺子进行打磨，即选择当前打磨一单位能带来最大斜边减少量的尺子。

附本人ac码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define mod 998244353
#define PLL pair<ll,ll>
const ll N=1e6+10;
double x[N],y[N];
priority_queue<pair<double,int>> pq;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll n,w;
	cin>>n>>w;
    for(int i=1;i<=n;i++)
	{
        cin>>x[i]>>y[i];
        double z=y[i]/sqrt(x[i]*x[i]+y[i]*y[i]);// 初始化：计算每把尺子的初始边际收益
        pq.push({z,i});
    }
    while(w!=0)
	{
        pair<double,int>it=pq.top(); 
        pq.pop();
        ll m=it.second;
        if(y[m]>0)
		{
            y[m]--;
            w--;
            double z=y[m]/sqrt(x[m]*x[m] + y[m]*y[m]);
            pq.push({z,m});
        }
        else if(y[m]==0)
		{
            if(!pq.empty())
			{
                break;
            }
        }
    }
    double sum=0;
    for(int i=1;i<=n;i++)
	{
        sum+=sqrt(x[i]*x[i]+y[i]*y[i]);
    }
    cout<<fixed<<setprecision(10)<<sum;
    return 0;
}