UVa10881

/* 解题的关键在于两点： 1.理解相撞就是擦肩而过，但是两者头上的记号会交换。 2.关键是确定相对顺序，并且正确编号，而蚂蚁的相对顺序是不变的。 因此首先使用id数组记录蚂蚁的相对顺序，即按照蚂蚁的初始位置为蚂蚁编号排序 之后计算最终蚂蚁的位置，然后改变蚂蚁的状态 最后根据相对顺序确定蚂蚁编号。 */ #include<cstdio> #include<iostream> #include<algorithm> #include<stdio.h> #include<vector> #include<utility> using namespace std; struct ele{ int id; int pos; char dir; bool operator <(const ele& a)const{ return id<a.id; } }; const int nmax=10000+5; ele ant[nmax]; int kase,n,L,T; int main() { //auto fin=fopen("UVa.in","r"); auto cmp_id=[](pair<int,int>&a,pair<int,int>&b){return a.second<b.second;}; auto cmp_pos=[](ele &a,ele&b){return a.pos<b.pos;}; //fscanf(fin,"%d",&kase); scanf("%d",&kase); for(int num=1;num<=kase;++num){ printf("Case #%d:\n",num); //fscanf(fin,"%d %d %d",&L,&T,&n); scanf("%d %d %d",&L,&T,&n); vector<pair<int,int>>id(n); for(int i=0;i<n;++i){ id[i].first=i+1; //fscanf(fin,"%d %c",&(id[i].second),&(ant[i].dir)); scanf("%d %c",&(id[i].second),&(ant[i].dir)); ant[i].pos=id[i].second; } sort(id.begin(),id.end(),cmp_id); for(int i=0;i<n;++i)ant[i].pos+=ant[i].dir=='R'?T:-T; sort(ant,ant+n,cmp_pos); for(int i=0;i<n;++i)ant[i].id=id[i].first; for(int i=0;i<n;++i){ if(ant[i].pos<0||ant[i].pos>L)ant[i].dir='F'; else if(i+1<n&&ant[i].pos==ant[i+1].pos){ ant[i].dir=ant[i+1].dir='T'; ++i; } } sort(ant,ant+n); for(int i=0;i<n;++i){ if(ant[i].dir=='F')printf("Fell off\n"); else if(ant[i].dir=='T')printf("%d Turning\n",ant[i].pos); else printf("%d %c\n",ant[i].pos,ant[i].dir); } printf("\n"); } return 0; }