标签：begin end min -- 抓拍 ans calc
- 果然还是分类讨论有疏漏：未考虑到两段移动区间“迎头相撞”的情况，思维要更加缜密
- 更简洁的做法是，考察周长关于时间的函数，通过三分法找极小值点
- abs和llabs都可以将long long类型的数取绝对值，其区别在于，若令x=-2147483648,llabs可以正常得到2147483648的结果，而abs不能
点击查看代码
#include <bits/stdc++.h>
using namespace std;
vector<int> x,y;
vector<int>a[5];
int q[205],n;
const int dx[]={0,1,-1,0,0};
const int dy[]={0,0,0,-1,1};
struct t1
{
long long x,y,opt;
}t[200005];
long long calc(long long T)
{
if(T<0)
{
T=-T;
}
long long maxx=LLONG_MIN,minx=LLONG_MAX,maxy=LLONG_MIN,miny=LLONG_MAX;
for(int i=1;i<=n;i++)
{
t[i].x+=(dx[t[i].opt]*T);
t[i].y+=(dy[t[i].opt]*T);
maxx=max(maxx,t[i].x);
minx=min(minx,t[i].x);
maxy=max(maxy,t[i].y);
miny=min(miny,t[i].y);
t[i].x-=(dx[t[i].opt]*T);
t[i].y-=(dy[t[i].opt]*T);
}
return 2*(maxx-minx+maxy-miny);
}
int main()
{
q['E']=1;q['W']=2;q['S']=3;q['N']=4;
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
int u,v;
char c;
cin>>u>>v>>c;
t[i].x=u;
t[i].y=v;
t[i].opt=q[c];
if(q[c]<=2)
{
a[q[c]].push_back(u);
}
else
{
a[q[c]].push_back(v);
}
if(c=='E'||c=='W')
{
y.push_back(v);
}
else
{
x.push_back(u);
}
}
sort(x.begin(),x.end());
sort(y.begin(),y.end());
for(int i=1;i<=4;i++)
{
sort(a[i].begin(),a[i].end());
}
long long ans=calc(0);
if(x.size()!=0)
{
int lx=*x.begin(),rx=*(--x.end());
for(int i=1;i<=2;i++)
{
if(a[i].size()>0)
{
ans=min(ans,calc(lx-*(a[i].begin())));
ans=min(ans,calc(rx-*(a[i].begin())));
ans=min(ans,calc(lx-*(--a[i].end())));
ans=min(ans,calc(rx-*(--a[i].end())));
}
}
}
if(a[1].size()>0&&a[2].size()>0)
{
int lx=*a[1].begin(),rx=*(--a[1].end());
ans=min(ans,calc((lx-*(a[2].begin()))/2));
ans=min(ans,calc((rx-*(a[2].begin()))/2));
ans=min(ans,calc((lx-*(--a[2].end()))/2));
ans=min(ans,calc((rx-*(--a[2].end()))/2));
ans=min(ans,calc((lx-*(a[2].begin()))/2+1));
ans=min(ans,calc((rx-*(a[2].begin()))/2+1));
ans=min(ans,calc((lx-*(--a[2].end()))/2+1));
ans=min(ans,calc((rx-*(--a[2].end()))/2+1));
}
if(y.size()!=0)
{
int ly=*y.begin(),ry=*(--y.end());
for(int i=3;i<=4;i++)
{
if(a[i].size()>0)
{
ans=min(ans,calc(ly-*(a[i].begin())));
ans=min(ans,calc(ry-*(a[i].begin())));
ans=min(ans,calc(ly-*(--a[i].end())));
ans=min(ans,calc(ry-*(--a[i].end())));
}
}
}
if(a[3].size()>0&&a[4].size()>0)
{
int lx=*a[3].begin(),rx=*(--a[3].end());
ans=min(ans,calc((lx-*(a[4].begin()))/2));
ans=min(ans,calc((rx-*(a[4].begin()))/2));
ans=min(ans,calc((lx-*(--a[4].end()))/2));
ans=min(ans,calc((rx-*(--a[4].end()))/2));
ans=min(ans,calc((lx-*(a[4].begin()))/2+1));
ans=min(ans,calc((rx-*(a[4].begin()))/2+1));
ans=min(ans,calc((lx-*(--a[4].end()))/2+1));
ans=min(ans,calc((rx-*(--a[4].end()))/2+1));
}
cout<<ans<<endl;
return 0;
}
标签：begin,
end,
min,
--,
抓拍,
ans,
calc
From： https://www.cnblogs.com/watersail/p/18326825