【CH6803】导弹防御塔

题目大意：给定 N 座塔，M 个怪物，每座塔一次可以发射一枚导弹，发射导弹有发射时间和冷却时间，每座塔和每只怪物有自己的二维坐标，所有导弹有一个共同的速度，求至少需要多长时间才能将所有怪物消灭。

题解：考虑若在 x 的时间可以消灭所有怪物，则大于 x 的时间也一定可以消灭所有怪物，因此考虑二分答案。

每个怪物只能被一枚导弹击中，而在 mid 时间内每座防御他能够发射的导弹数量也是固定的，考虑将每座塔拆分成固定数目的点，之后与怪物集合进行匹配，若怪物集合中每个点均被匹配成功，则符合条件，反之则不符合条件。

代码如下

#include <bits/stdc++.h>

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define all(x) x.begin(),x.end()

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

const int dx[]={0,1,0,-1};

const int dy[]={1,0,-1,0};

const int mod=1e9+7;

const int inf=0x3f3f3f3f;

//const int maxn=2600;

const double eps=1e-8;

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll sqr(ll x){return x*x;}

inline ll read(){

	ll x=0,f=1;char ch;

	do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));

	do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));

	return f*x;

}

/*--------------------------------------------------------*/

vector<int> G[51];

int n,m,tot,match[2501];bool vis[2501];

double t1,t2,vol;

struct point{double x,y;}tow[51],mon[51];

struct node{int id;double t;}ver[2501];

inline double dis(const point &a,const point &b){

	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

void read_and_parse(){

	scanf("%d%d%lf%lf%lf",&n,&m,&t1,&t2,&vol),t1/=60;

	for(int i=1;i<=m;i++)scanf("%lf%lf",&mon[i].x,&mon[i].y);

	for(int i=1;i<=n;i++)scanf("%lf%lf",&tow[i].x,&tow[i].y);

	tot=n*m;

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

		for(int j=1;j<=m;j++)

			ver[(i-1)*m+j].id=i,ver[(i-1)*m+j].t=(j-1)*(t1+t2)+t1;

}

bool dfs(int u){

	for(auto v:G[u])if(!vis[v]){

		vis[v]=1;

		if(!match[v]||dfs(match[v])){

			match[v]=u;return 1;

		}

	}

	return 0;

}

bool right(double mid){

	for(int i=1;i<=m;i++)G[i].clear();

	memset(match,0,sizeof(match));

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

		for(int j=1;j<=tot;j++)

			if(ver[j].t+dis(tow[ver[j].id],mon[i])/vol<=mid)G[i].pb(j);

	for(int i=1;i<=m;i++){

		memset(vis,0,sizeof(vis));

		if(!dfs(i))return 0;

	}

	return 1;

}

void solve(){

	double l=t1,r=1e5;

	while(r-l>eps){

		double mid=(l+r)/2;

		if(right(mid))r=mid;

		else l=mid;

	}

	printf("%.6lf\n",r);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【CH6803】导弹防御塔

最新文章

热门文章