pku1434.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 73 行

#include <stdio.h>

typedef struct 
{
	int h;
	int flag;
	int id;
} H;

H level[100000];

int cmp(const void *a, const void *b)
{
	H *aa = (H *)a;
	H *bb = (H *)b;
	return aa->h - bb->h;
}

int main()
{
	int b, h, w, d, s[50000], V, t, s_sum, tV;
	int n, i;
	double L;

	scanf("%d", &t);

	while (t--)
	{
		scanf("%d", &n);
		for (i = 0; i < n; i++)
		{
			scanf("%d%d%d%d", &b, &h, &w, &d);
			s[i] = w * d;
			level[2*i].h = b;
			level[2*i].flag = 1;
			level[2*i].id = i;

			level[2*i+1].h = b + h;
			level[2*i+1].flag = -1;
			level[2*i+1].id = i;
		}
		scanf("%d", &V);
		qsort(level, 2 * n, sizeof(level[0]), cmp);
		
		for (i = 0, s_sum = 0; i < 2 * n - 1; i++)
		{
			s_sum += s[level[i].id] * level[i].flag;

			tV = s_sum * (level[i+1].h - level[i].h);
			if (V > tV)
			{
				V -= tV;
			}
			else
			{
				break;
			}
		}
		if (i >= 2 * n - 1)
		{
			printf("OVERFLOW\n");
		}
		else
		{
			L = level[i].h + (double)V / s_sum;
			printf("%.2lf\n", L);
		}
	}
	
	return 0;
}