首页 > 代码库 > UvaLive6662 The Last Ant 模拟
UvaLive6662 The Last Ant 模拟
UvaLive6662
PDF题目
题意：给出隧道长度L，蚂蚁数量N，各蚂蚁位置Pi、前进方向Di，都为整数（前进方向为L或R），蚂蚁速度为1cm每秒，两蚂蚁若在整数点相遇则都反向，若不在整数点相遇则继续向前。求最后一个走出隧道的蚂蚁的编号。蚂蚁按编号1~n给出，隧道头尾位置为0和L。
题解：
模拟。
当然我们不用模拟蚂蚁实时行走，我们只用算一算蚂蚁什么时候会撞到。
给蚂蚁建个结构体，包括编号、位置、方向，方便以后操作。因为蚂蚁起始位置为整数，也总会在整数点相遇，所以所有数据都可以整数存储。
先给蚂蚁排个序，第一关键字位置，第二关键字方向，排完序后位置数值越小的在数组越前面，位置相同的L在R的前面。然后我们对每个蚂蚁进行研究，向它前进的方向找第一个与它反向而且会和它在整数点相遇的蚂蚁，跳出。记录其中最小的整数点相撞时间mint，判完所有蚂蚁后，让蚂蚁们走过mint，然后排序，将现在相同位置的蚂蚁转向。
重复上面的操作，直到没有蚂蚁会相撞。此时计算各蚂蚁出局时间，找出最后的蚂蚁，输出它的编号和总时间。
题目保证蚂蚁都会出去，不会撞死在里面。
题目没说超过2个蚂蚁撞到一起会怎么样，我是也考虑了，全部转向，不懂有没有这样的数据。
1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set> 10 #include<stack> 11 #include<queue> 12 using namespace std; 13 #define ll __int64 14 #define usint unsigned int 15 #define mz(array) memset(array, 0, sizeof(array)) 16 #define minf(array) memset(array, 0x3f, sizeof(array)) 17 #define REP(i,n) for(int i=0;i<(n);i++) 18 #define FOR(i,x,n) for(int i=(x);i<=(n);i++) 19 #define RD(x) scanf("%d",&x) 20 #define RD2(x,y) scanf("%d%d",&x,&y) 21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 22 #define WN(x) printf("%d\n",x); 23 #define RE freopen("D.in","r",stdin) 24 #define WE freopen("1biao.out","w",stdout) 25 26 const int inf=0x3f3f3f3f; 27 const int maxn=22; 28 29 struct ant { 30 int num; 31 char d; 32 int p; 33 }; 34 35 int n,l; 36 ant a[maxn]; 37 38 bool operator <(ant x,ant y) { 39 if(x.p!=y.p)return x.p<y.p; 40 else return x.d<y.d; 41 } 42 43 void del(ant a[],const int &i,int &m) { 44 for(int j=i; j<m-1; j++) 45 a[j]=a[j+1]; 46 m--; 47 } 48 49 void check(int m) { 50 for(int q=0; q<m; q++) 51 printf("%d.(%c,%d) ",a[q].num,a[q].d,a[q].p); 52 puts(""); 53 } 54 55 int main() { 56 int i,j,k; 57 while(scanf("%d%d",&n,&l)!=EOF) { 58 if(n==0 && l==0)break; 59 60 for(i=0; i<n; i++) { 61 scanf(" %c%d",&a[i].d,&a[i].p); 62 a[i].num=i+1; 63 } 64 65 sort(a,a+n); 66 int m=n; 67 int time=0; 68 while(m>=1) {///还剩蚂蚁 69 int mint=inf; 70 for(i=0; i<m; i++) 71 if(a[i].d==‘L‘) { 72 for(j=i-1; j>=0; j--) 73 if(a[j].d==‘R‘ && ((a[j].p+a[i].p)&1)==0) { 74 int tt=abs(a[j].p-a[i].p)/2; 75 if(tt<mint) mint=tt;///记录会撞上的最小时间 76 break; 77 } 78 } else ///a[i].d==‘R‘ 79 for(j=i+1; j<m; j++) 80 if(a[j].d==‘L‘ && ((a[j].p+a[i].p)&1)==0) {///(..&1)==0，省括号会逗，&优先级很低的样子 81 int tt=abs(a[j].p-a[i].p)/2; 82 if(tt<mint) mint=tt; 83 break; 84 } 85 if(mint!=inf) {///有蚂蚁会撞上 86 for(i=0; i<m; i++)///让蚂蚁走过mint的时间撞上 87 if(a[i].d==‘L‘)a[i].p-=mint; 88 else a[i].p+=mint; 89 sort(a,a+m);///排序，将相同位置的蚂蚁挪到一起 90 for(i=m-1; i>=0; i--)///删掉走出去的蚂蚁 91 if((a[i].p<0) || (a[i].p>l)) del(a,i,m); 92 i=1; 93 while(i<m) {///把位置相同的蚂蚁全部转个向 94 if(a[i].p==a[i-1].p&& a[i].d!=a[i-1].d) { 95 j=i+1; 96 while(j<m&& a[j].p==a[i].p)j++; 97 for(k=i-1; k<j; k++) 98 if(a[k].d==‘L‘)a[k].d=‘R‘; 99 else a[k].d=‘L‘;100 i=j+1;101 } else i++;102 }103 // check(m);104 sort(a,a+m);///排个序，让位置相同的蚂蚁往左的在左边，往右的在右边，不会撞105 time+=mint;///统计经过的时间106 } else { ///没蚂蚁会相撞了，找出最晚跑出去的蚂蚁107 int maxi=-1;108 int maxt=-1;109 for(i=0; i<m; i++) {110 if(a[i].d==‘L‘ && a[i].p>=maxt) {111 maxt=a[i].p;112 maxi=i;113 } else if(a[i].d==‘R‘ && (l-a[i].p>maxt)) {114 maxt=l-a[i].p;115 maxi=i;116 }117 // printf("%f,%d ",maxt,maxi);118 }119 printf("%d %d\n",maxt+time,a[maxi].num);120 m=0;121 }122 }123 }124 return 0;125 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。