首页 > 代码库 > POJ 1852 Ants 分析
POJ 1852 Ants 分析
1、暴搜
每只蚂蚁朝向有两种，可以枚举n只蚂蚁的朝向，然后模拟蚂蚁相遇的情景，总共2^n中情况。
2、分析ants相碰的情况:
(a->) (<-b) 变成 (<-a)(b->)
由于每只蚂蚁是相同的，所以等价与(<-b)(a->)，这和两只蚂蚁原来的走向是一样的，即把碰撞当作没发生过
所以可以对每一只蚂蚁检查一次就可以了
3、空间优化
存蚂蚁的初始位置O(n),但是我们每次只要比较 a[i] 和 len-a[i] 就可以了，后面不需要这两个值了，所以完全可以用一个x来存ant position，空间O(1)
最终每一次 时间O(n) 空间O(1)
/* 贪心，挑战程序设计竞赛 巫 */#include<cstdio>int min(int a,int b){ return a<b?a:b;}int main(){ int T,len,n,x,minn,maxn,tmp; scanf("%d",&T); while(T--){ scanf("%d %d",&len,&n); minn=-1111111,maxn=-11111; while(n--){ scanf("%d",&x); tmp=min(x,len-x); /* smaller one */ if(tmp>minn) minn=tmp; tmp=len-tmp; /* bigger one */ if(tmp>maxn) maxn=tmp; } printf("%d %d\n",minn,maxn); } return 0;}
POJ 1852 Ants 分析
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。