Codeforces 424 B Megacity【贪心】

时间:2021-05-10 03:11:12

题意:给出城市(0,0),给出n个坐标,起始人数s,每个坐标k个人, 每个坐标可以覆盖到半径为r的区域,r=sqrt(x*x+y*y)的区域,问最小的半径是多少,使得城市的总人数大于等于1000000

最开始是排序,贪心来做的,发现sqrt的精度老达不到要求,于是翻了代码

于是发现用map就可以解决了

map<int,int>,it->first是第一个int的内容,it->second是第二个int的内容

话说本来是按照标签来找的,想做二分查找的题目的= =

 #include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
using namespace std; typedef long long LL;
const int INF = (<<)-;
const int mod=;
const int maxn=; int main(){
int n,s;
map<int,int> cnt;
scanf("%d %d",&n,&s);
int x,y,k;
for(int i=;i<=n;i++){
cin>>x>>y>>k;
cnt[x*x+y*y]+=k;
} for(map<int,int>::iterator it=cnt.begin();it!=cnt.end();++it){
s+=it->second;
if(s>=){
printf("%lf\n",sqrt(it->first));
return ;
}
}
printf("-1\n");
return ;
}