【推导】【分类讨论】Codeforces Round #431 (Div. 1) B. Rooter's Song

给你一个这样的图，那些点是舞者，他们每个人会在原地待ti时间之后，以每秒1m的速度向前移动，到边界以后停止。只不过有时候会碰撞，碰撞之后的转向是这样哒：

让你输出每个人的停止位置坐标。

①将x轴上初始坐标记为(pi,0)，y轴上的初始坐标记为(0,pi)。只有pi-ti相同的才有可能发生碰撞。于是可以按照这一点将人划分为很多组，不同组之间绝对不会互相影响。

②假设一组内每个人都不会发生碰撞，那么所有的路线交叉点都是碰撞点。所以碰撞次数可能达到n^2次，暴力不可行。

③对于一组内，形成了一个网格图，每个人往哪走其实可以O（1）推算。

如图这是同一组内的情况，可以看到，对于x轴上的初始点，它走到的位置只与其右侧的竖线数和上方的横线数的大小关系有关。y轴上的初始点同理可得。

于是对于一组内，可以把x轴上的和y轴上的分别按p从小到大排序，然后讨论一下就能获得答案啦。

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

struct Point{

	int p,id;

	Point(const int &p,const int &id){

		this->p=p;

		this->id=id;

	}

	Point(){}

};

bool cmp(const Point &a,const Point &b){

	return a.p<b.p;

}

vector<Point>v[200005][2];

typedef pair<int,int> pii;

pii anss[100005];

int n,w,h;

int main(){

	//freopen("b.in","r",stdin);

	int op,P,K;

	scanf("%d%d%d",&n,&w,&h);

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

		scanf("%d%d%d",&op,&P,&K);

		v[P-K+100000][op-1].push_back(Point(P,i));

	}

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

		sort(v[i][0].begin(),v[i][0].end(),cmp);

		sort(v[i][1].begin(),v[i][1].end(),cmp);

		for(int j=0;j<v[i][0].size();++j){

			if(v[i][0].size()-j-1>=v[i][1].size()){

				anss[v[i][0][j].id]=make_pair(v[i][0][j+v[i][1].size()].p,h);

			}

			else{

				anss[v[i][0][j].id]=make_pair(w,v[i][1][v[i][0].size()-1-j].p);

			}

		}

		for(int j=0;j<v[i][1].size();++j){

			if(v[i][0].size()>=v[i][1].size()-j){

				anss[v[i][1][j].id]=make_pair(v[i][0][v[i][1].size()-1-j].p,h);

			}

			else{

				anss[v[i][1][j].id]=make_pair(w,v[i][1][j+v[i][0].size()].p);

			}

		}

	}

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

		printf("%d %d\n",anss[i].first,anss[i].second);

	}

	return 0;

}

巴特西

【推导】【分类讨论】Codeforces Round #431 (Div. 1) B. Rooter's Song

最新文章

热门文章