新乡网站建设哪家专业,建行企业手机银行下载安装,wordpress首页登录,163 com邮箱注册1、暴搜 每只蚂蚁朝向有两种#xff0c;可以枚举n只蚂蚁的朝向#xff0c;然后模拟蚂蚁相遇的情景#xff0c;总共2^n中情况。 2、分析ants相碰的情况: (a-) (-b) 变成 (-a)(b-) 由于每只蚂蚁是相同的#xff0c;所以等价与(-b)(a-)#xff0c;…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) /* 贪心挑战程序设计竞赛 巫 */
#includecstdioint min(int a,int b){ return ab?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);tmpmin(x,len-x); /* smaller one */if(tmpminn) minntmp;tmplen-tmp; /* bigger one */if(tmpmaxn) maxntmp;}printf(%d %d\n,minn,maxn);}return 0;
} 转载于:https://www.cnblogs.com/tinyork/p/4268502.html
