正題

---

大意

有n只螞蟻，他們會往固定方向行走，行走速度相同，如果兩只或多只相撞就會消除，求所有碰撞后剩余的螞蟻數量

---

解題思路

將兩只會相撞的螞蟻碰撞的信息記錄下來（包括需要多久后碰撞），然后將時間從小到大排序。

接下來要解決多只碰撞的問題，用兩個數組表示以消除和已經有碰撞，然后如果發現這次的時間已經和上次的不一樣了，就把已經碰撞的都標記為以消除。

---

代碼

代碼極丑無比
以下內容可能會引起你的不舒適，請選擇性觀看

include<cstdio> #include<algorithm> #include<iostream> using namespace std; struct xjq/*啦啦啦啦啦*/{int fi,sn;double w; }dis[2501]; int tot,n,ans; double x[51],y[51],s; char c[51]; bool tmp[51],e[51]; double abs(double x) {if (x<0) return -x;else return x; } bool cmp(xjq x,xjq y)//排序用 {return x.w<y.w; } int main() {scanf("%d",&n);scanf("\n");for (int i=1;i<=n;i++){cin>>c[i];}for (int i=1;i<=n;i++){scanf("%lf%lf",&x[i],&y[i]);}for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){if (i==j) continue;if (x[i]==x[j] && y[i]==y[j]) //好像不會有這種情況，可以無視{dis[++tot].fi=i;dis[tot].sn=j;dis[tot].w=0;}else if (y[i]==y[j] && ((x[i]<x[j] && c[i]=='E' && c[j]=='W') || (x[i]>x[j] && c[i]=='W' && c[j]=='E')))//東西相撞{dis[++tot].fi=i;dis[tot].sn=j;dis[tot].w=abs(x[i]-x[j])/2;}else if (x[i]==x[j] &&((y[i]>y[j] && c[i]=='S' && c[j]=='N') || (y[i]<y[j] && c[i]=='N' && c[j]=='S')))//南北相撞{dis[++tot].fi=i;dis[tot].sn=j;dis[tot].w=abs(y[i]-y[j])/2;}else if (abs(x[i]-x[j])==abs(y[i]-y[j]))//直角相撞{if ((x[i]<x[j] && y[i]<y[j] && ((c[i]=='E' && c[j]=='S') || (c[i]=='N' && c[j]=='W')))||(x[i]>x[j] && y[i]>y[j] && ((c[i]=='W' && c[j]=='N') || (c[i]=='S' && c[j]=='E')))||(x[i]<x[j] && y[i]>y[j] && ((c[i]=='E' && c[j]=='N') || (c[i]=='S' && c[j]=='W')))||(x[i]>x[j] && y[i]<y[j] && ((c[i]=='W' && c[j]=='S') || (c[i]=='N' && c[j]=='E')))){dis[++tot].fi=i;dis[tot].sn=j;dis[tot].w=abs(y[i]-y[j]);}}}}ans=n;sort(dis+1,dis+tot+1,cmp);//排序for (int i=1;i<=tot;i++){if (dis[i].w>s){s=dis[i].w;for (int j=1;j<=n;j++)e[j]=tmp[j];//賦值}if (!e[dis[i].fi] && !e[dis[i].sn]){if (!tmp[dis[i].fi]) ans--;if (!tmp[dis[i].sn]) ans--;tmp[dis[i].fi]=true;tmp[dis[i].sn]=true;//printf("%d %d %lf\n",dis[i].fi,dis[i].sn,dis[i].w);}}printf("%d",ans); }

總結

以上是生活随笔為你收集整理的【2018.4.14】模拟赛之二-ssl2392 蚂蚁【图论】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。