LOJ #10002. 喷水装置

裸的贪心。

基本思想见图:

Code:



#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N = 15001;

int T;

int cnt,n,L,W;

int ans;

struct rou

{

	int l;

	int r;

}a[N];

bool cmp(rou x,rou y)

{

	return x.l<y.l;

}

void work()

{

	cnt=0;

	ans=0;

   //这是一个很日学的东西，卡了我一个星期。

   //以后一看见“有多组数据”，就想到work函数内付0.

	scanf("%d%d%d",&n,&L,&W);

	for(int i=1;i<=n;++i)

	{

		int C,R;

		scanf("%d%d",&C,&R);

		if(2*R<=W)

			continue;

		a[++cnt].l=C-sqrt(R*R-W*W/4.0);

		a[cnt].r=C+sqrt(R*R-W*W/4.0);

	}

	sort(a+1,a+cnt+1,cmp);

	int t=0;

	while(t<L)

	{

		++ans;

		int s=t;

		for(int i=1;i<=cnt;++i)

			if(a[i].l<=s&&t<a[i].r)

				t=a[i].r;

		if(t==s&&t<L)

		{

			printf("-1\n");

			return;

		}

	}

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

}

int main()

{

	scanf("%d",&T);

	for(int t=1;t<=T;++t)

		work();

	return 0;

}

血泪啊！

一定要吸取教训啊！！

啊！！！

巴特西

LOJ #10002. 喷水装置

裸的贪心。

最新文章

热门文章