Contest Hunter #46 T1 磁力块 [花式暴力]

将所有石头按距离远近排序，将所有取到的时候扔进堆里维护最大磁力强度。

贪心，每次用强度最强的磁石尝试吸引地上的石头，扫完区间以后，这块石头就再也不会用到了。

在此基础上可以做些小优化，比如说优化未取石头区间的起始点，比如说如果强度更小的石头范围也更小就不用它，等等。

比标解分块跑得还要快2333333

分块解法链接：http://www.cnblogs.com/SilverNebula/p/5929668.html

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #define LL long long

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 struct stone{

     double dis;

     int m,p,r;

     bool got;

 }s[mxn];

 bool operator < (stone a,stone b){

     return a.dis<b.dis;

 }

 struct tool{

     int r,p;

 }t[mxn];int cnt=;

 bool operator < (tool a,tool b){

     return a.p<b.p;

 }

 priority_queue<tool>tp;

 double dist(double x1,double y1,double x2,double y2){

     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

 }

 int n;

 int x,y;

 int main(){

     int x0,y0;

     scanf("%d%d%d%d%d",&x0,&y0,&t[].p,&t[].r,&n);

     int i,j;

     for(i=;i<=n;i++){

 //        scanf("%d%d%d%d%d",&x,&y,&s[i].m,&s[i].p,&s[i].r);

         x=read();y=read();s[i].m=read();s[i].p=read();s[i].r=read();

         s[i].dis=dist(x0,y0,x,y);

         s[i].got=;

     }

     sort(s+,s+n+);

 //    for(i=1;i<=n;i++)printf("dis:%.3f  m:%d  r:%d p:%d\n",s[i].dis,s[i].m,s[i].r,s[i].p);

 //    printf("finished\n");

     tp.push(t[]);

     int hd=;

     int last=;

     int lastp=;

     while(!tp.empty()){

         tool now=tp.top();tp.pop();

         if(last>=now.r && lastp>=now.p)continue;

         for(register int i=hd;i<=n && s[i].dis<=(double)now.r;i++){

             if(!s[i].got && now.p>=s[i].m){

                 cnt++;

                 t[cnt].p=s[i].p;

                 t[cnt].r=s[i].r;

                 tp.push(t[cnt]);

                 s[i].got=;

             }

         }

         while(s[hd].got)hd++;

         last=now.r;

         lastp=now.p;

     }

     printf("%d\n",cnt);

     return ;

 }