樱桃蛋糕

第一行一个正整数 $\text n$ ，代表商人的数量。
接下来 $\text n$ 行三个空格分隔的正整数 $x_{i},y_{i},dir_{i}$ ,分别代表商人在时刻 $\text 0$ 所在的坐标和他移动的方向。
$1\leq n \leq 5000$
$1\leq x_{i},y_{i} \leq 10^{8}$
$dir_{i}\in {\lbrace 1,2,3,4 \rbrace}$
当 $dir_{i}=1$ 时，代表商人向上移动。
当 $dir_{i}=2$ 时，代表商人向下移动。
当 $dir_{i}=3$ 时，代表商人向右移动。
当 $dir_{i}=4$ 时，代表商人向左移动。

C++14(g++5.4) 解法, 执行用时: 146ms, 内存消耗: 508K, 提交时间: 2020-05-30 14:36:27

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5010;
int n,d[N];
int x[N],y[N];
double check(int i,int t,int d)
{
	double dx,dy;
	if(d==1) 
	{
		dx=fabs(x[i]); dy=y[i]+t;
		if(dy>0) return -1;
		else 
		{
			if(dy>=dx) return (dx+dy)/2;
			else return -1;
		}
	}
	else if(d==2)
	{
		dx=fabs(x[i]); dy=y[i]-t;
		if(dy<0) return -1;
		else 
		{
			if(dy>=dx) return (dx+dy)/2;
			else return -1;
		}
	}
	else if(d==3)
	{
		dy=fabs(y[i]); dx=x[i]+t;
		if(dx>0) return -1;
		else 
		{
			dx=-dx;
			if(dy<=dx) return (dx+dy)/2;
			else return -1;
		}
	}
	else
	{
		dy=fabs(y[i]); dx=x[i]-t;
		if(dx<0) return -1;
		else 
		{
			if(dy<=dx) return (dx+dy)/2;
			else return -1;
		}
	}
} 
bool st[N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i]>>d[i];
	}
	int ans=0,t=0;
	for(int i=1;i<=n;i++)
	{
		double res=1e9;
		int l;
		for(int j=1;j<=n;j++)
			if(!st[j]&&check(j,t,d[j])!=-1)
			{
				double ch=check(j,t,d[j]);
				if(ch<res)
				{
					res=ch;
					l=j;
				}
			}
		if(res==1e9) break;
		else
		{
			ans++;
			st[l]=1;
			t+=res*2;
		}
	}
	cout<<ans;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 608K, 提交时间: 2020-06-28 16:27:38

#include<bits/stdc++.h>
using namespace std;

struct node
{
	int cost,r;
}R[5005];
bool cmp(node a,node b)
{
	return a.cost<b.cost;
}
int main()
{
	int i,j,ans=0,n,L=0,d;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d%d%d",&i,&j,&d);
		if(d&1)continue;
		if(d==2&&j>=i)R[L].r=j-i,R[L++].cost=i+j;
		if(d==4&&i>=j)R[L].r=i-j,R[L++].cost=i+j;
	}
	sort(R,R+L,cmp);
	for(i=j=0;i<L;i++)if(j<=R[i].r)ans++,j=R[i].cost;
	printf("%d\n",ans);
}

详情