1434.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"stdio.h"
#include"algorithm"
using namespace std;

long s[50000];
long h_b[50000];
long h_t[50000];
long h[100000];
long index_b[50000];
long index_t[50000];

long n,v,m;
int cmp_b(long a,long b)
{return h_b[a]<h_b[b];}

int cmp_t(long a,long b)
{return h_t[a]<h_t[b];}


void init()
{long i,j=0,a,b,c;
cin>>n;
for(i=0;i<n;i++)
{cin>>h_b[i]>>a>>b>>c;
s[i]=b*c;
h_t[i]=h_b[i]+a;

h[j++]=h_b[i];
h[j++]=h_t[i];
index_b[i]=i;
index_t[i]=i;
}
m=j;
sort(&index_b[0],&index_b[n],cmp_b);
sort(&index_t[0],&index_t[n],cmp_t);
sort(&h[0],&h[m]);
cin>>v;
}

long pt,pb;

double doit()
{long i;_int64 ss=0;
pt=pb=0;

for(i=0;i<m;i++)
{if(i){if(v<=ss*(h[i]-h[i-1]))break;v-=ss*(h[i]-h[i-1]);}
     if(h_b[index_b[pb]]==h[i])ss+=s[index_b[pb++]];
else if(h_t[index_t[pt]]==h[i])ss-=s[index_t[pt++]];
}

if(i==m)return -1;
else return double(v)/ss+h[i-1];
}

int main()
{int t;double f;
cin>>t;
while(t--)
{init();
f=doit();
if(f>0)printf("%.2f\n",f);
else printf("OVERFLOW\n");
}
return 0;
}