A题通过率95%WA求大佬调
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
typedef long long ll;
//先打磨可以带来最多斜边长度减少量的直角边
long double x[N], y[N];
struct item{
int id;
long double delta;
};
struct compare{
bool operator()(item a, item b){
return a.delta < b.delta;
}
};
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
priority_queue<item, vector<item>, compare> pq;
int n, w;
cin >> n >> w;
for(int i = 1; i <= n; i ++){
cin >> x[i] >> y[i];
pq.push({i, fabs(sqrt(pow(x[i], 2) + pow(y[i], 2)) - sqrt(pow(x[i], 2) + pow(y[i] - 1, 2)))});
}
item t = pq.top();
//模拟打磨过程
while(w > 0 && y[t.id] > 0){
t = pq.top();
pq.pop();
//t是要打磨的尺子
w -= 1;
y[t.id] -= 1;
t.delta = fabs(sqrt(pow(x[t.id], 2) + pow(y[t.id], 2)) - sqrt(pow(x[t.id], 2) + pow(y[t.id] - 1, 2)));//更新delta
pq.push(t);
}
long double ans = 0;
while(!pq.empty()){
item t = pq.top();
pq.pop();
if(y[t.id] != 0) ans += (sqrt(fabs(x[t.id] * x[t.id] + y[t.id] * y[t.id])));
else ans += x[t.id];
}
cout << fixed << setprecision(18) << ans;
return 0;
}